Submission #1415603
Source Code Expand
#include <cstdio> #include <cstring> #include <set> #include <queue> #include <vector> #include <algorithm> const int N = 100000 + 10; int n, a[N], b[N], c[N]; inline int f(int x) { return std::lower_bound(c, c + n + 1, x) - c; } int res, match[N]; int dist[N]; void bfs() { static int sum[N]; static std::vector<std::pair<int, int>> adj[N]; for (int i = 1; i <= n; ++i) { int j = match[i]; if (j >= a[i]) { ++sum[a[i]]; adj[b[i]].emplace_back(a[i], -1); } else { ++sum[b[i]]; adj[a[i]].emplace_back(b[i], 1); } --sum[j]; } for (int i = 1; i <= n; ++i) sum[i] += sum[i - 1]; for (int i = 0; i < n; ++i) if (sum[i]) adj[i].emplace_back(i + 1, 0); for (int i = 0; i < n; ++i) adj[i + 1].emplace_back(i, 0); memset(dist, -0x3f, sizeof dist); std::queue<int> q; static bool flag[N]; dist[0] = 0; for (q.push(0); !q.empty(); q.pop()) { int a = q.front(); flag[a] = false; for (auto it : adj[a]) { int b = it.first, c = it.second; if (dist[a] + c > dist[b]) { dist[b] = dist[a] + c; if (!flag[b]) q.push(b), flag[b] = true; } } } } int init() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i], &b[i]); for (int i = 0; i <= n; ++i) scanf("%d", &c[i]); std::sort(c, c + n + 1); for (int i = 1; i <= n; ++i) a[i] = f(a[i]), b[i] = f(b[i]); static std::pair<int, int> info[N]; for (int i = 1; i <= n; ++i) info[i] = {std::min(a[i], b[i]), i}; std::sort(info + 1, info + n + 1); std::set<std::pair<int, int>> pool; res = 0; for (int i = 1, j = 1; i <= n; ++i) { for (; j <= n && info[j].first <= i; ++j) pool.emplace(a[info[j].second], info[j].second); if (pool.empty()) { res = -1; break; } auto x = *pool.begin(); if (x.first > i) x = *pool.rbegin(); else ++res; match[x.second] = i; pool.erase(x); } if (res >= 0) bfs(); int q; scanf("%d", &q); return q; } int main() { for (int q = init(); q--;) { int d, e; scanf("%d%d", &d, &e); if (res < 0) puts("-1"); else printf("%d\n", std::max(-1, res + std::max(dist[f(d)] + 1, dist[f(e)]))); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Two Faced Cards |
User | jiaqiyang |
Language | C++14 (GCC 5.4.1) |
Score | 2000 |
Code Size | 2263 Byte |
Status | AC |
Exec Time | 424 ms |
Memory | 11520 KB |
Compile Error
./Main.cpp: In function ‘int init()’: ./Main.cpp:52:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &n); ^ ./Main.cpp:53:59: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i], &b[i]); ^ ./Main.cpp:54:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] for (int i = 0; i <= n; ++i) scanf("%d", &c[i]); ^ ./Main.cpp:75:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &q); ^ ./Main.cpp: In function ‘int main()’: ./Main.cpp:82:26: warning: ignoring return value of ‘int scanf...
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 2000 / 2000 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_49.txt, subtask_1_50.txt, subtask_1_51.txt, subtask_1_52.txt, subtask_1_53.txt, subtask_1_54.txt, subtask_1_55.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 3 ms | 4224 KB |
sample_02.txt | AC | 3 ms | 4224 KB |
sample_03.txt | AC | 2 ms | 4224 KB |
subtask_1_01.txt | AC | 88 ms | 8448 KB |
subtask_1_02.txt | AC | 73 ms | 7040 KB |
subtask_1_03.txt | AC | 47 ms | 6400 KB |
subtask_1_04.txt | AC | 66 ms | 7424 KB |
subtask_1_05.txt | AC | 69 ms | 5632 KB |
subtask_1_06.txt | AC | 105 ms | 8320 KB |
subtask_1_07.txt | AC | 74 ms | 3968 KB |
subtask_1_08.txt | AC | 100 ms | 9600 KB |
subtask_1_09.txt | AC | 216 ms | 8448 KB |
subtask_1_10.txt | AC | 57 ms | 7296 KB |
subtask_1_11.txt | AC | 38 ms | 3200 KB |
subtask_1_12.txt | AC | 54 ms | 6784 KB |
subtask_1_13.txt | AC | 139 ms | 7040 KB |
subtask_1_14.txt | AC | 43 ms | 6528 KB |
subtask_1_15.txt | AC | 52 ms | 3584 KB |
subtask_1_16.txt | AC | 34 ms | 5376 KB |
subtask_1_17.txt | AC | 311 ms | 9944 KB |
subtask_1_18.txt | AC | 34 ms | 6400 KB |
subtask_1_19.txt | AC | 62 ms | 3584 KB |
subtask_1_20.txt | AC | 116 ms | 9472 KB |
subtask_1_21.txt | AC | 193 ms | 11500 KB |
subtask_1_22.txt | AC | 144 ms | 9472 KB |
subtask_1_23.txt | AC | 195 ms | 11500 KB |
subtask_1_24.txt | AC | 143 ms | 9472 KB |
subtask_1_25.txt | AC | 420 ms | 10076 KB |
subtask_1_26.txt | AC | 144 ms | 9856 KB |
subtask_1_27.txt | AC | 92 ms | 4224 KB |
subtask_1_28.txt | AC | 152 ms | 10240 KB |
subtask_1_29.txt | AC | 402 ms | 11520 KB |
subtask_1_30.txt | AC | 143 ms | 9856 KB |
subtask_1_31.txt | AC | 91 ms | 4224 KB |
subtask_1_32.txt | AC | 148 ms | 10240 KB |
subtask_1_33.txt | AC | 405 ms | 10084 KB |
subtask_1_34.txt | AC | 144 ms | 9728 KB |
subtask_1_35.txt | AC | 92 ms | 4224 KB |
subtask_1_36.txt | AC | 149 ms | 10240 KB |
subtask_1_37.txt | AC | 424 ms | 10092 KB |
subtask_1_38.txt | AC | 144 ms | 9728 KB |
subtask_1_39.txt | AC | 93 ms | 4224 KB |
subtask_1_40.txt | AC | 150 ms | 10240 KB |
subtask_1_41.txt | AC | 170 ms | 10880 KB |
subtask_1_42.txt | AC | 136 ms | 10752 KB |
subtask_1_43.txt | AC | 204 ms | 10752 KB |
subtask_1_44.txt | AC | 136 ms | 10496 KB |
subtask_1_45.txt | AC | 80 ms | 4224 KB |
subtask_1_46.txt | AC | 156 ms | 10496 KB |
subtask_1_47.txt | AC | 129 ms | 10496 KB |
subtask_1_48.txt | AC | 143 ms | 10496 KB |
subtask_1_49.txt | AC | 132 ms | 10496 KB |
subtask_1_50.txt | AC | 74 ms | 4224 KB |
subtask_1_51.txt | AC | 3 ms | 4224 KB |
subtask_1_52.txt | AC | 3 ms | 4224 KB |
subtask_1_53.txt | AC | 3 ms | 4224 KB |
subtask_1_54.txt | AC | 3 ms | 4224 KB |
subtask_1_55.txt | AC | 3 ms | 4224 KB |