# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
660786 | 2022-11-23T08:42:58 Z | 600Mihnea | 중앙값 배열 (balkan11_medians) | C++17 | 84 ms | 12748 KB |
bool home = 0; #include <bits/stdc++.h> using namespace std; const int N = 200000 + 7; int n; int b[N]; int a[N]; set<int> s; int nxt_up(int i) { auto it = s.lower_bound(i); assert(it != s.end()); int sol = *it; s.erase(it); return sol; } int nxt_down(int i) { auto it = s.lower_bound(i + 1); assert(it != s.begin()); it--; int sol = *it; s.erase(it); return sol; } int main() { if (home == 0) { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); } else { freopen ("input.txt", "r", stdin); } cin >> n; for (int i = 1; i <= 2 * n - 1; i++) { s.insert(i); } for (int i = 1; i <= n; i++) { cin >> b[i]; } a[1] = nxt_up(b[1]); for (int i = 2; i <= n; i++) { if (b[i] == b[i - 1]) { a[2 * i - 2] = nxt_up(1); a[2 * i - 1] = nxt_down(2 * n - 1); continue; } if (b[i] < b[i - 1]) { if (s.count(b[i])) { a[2 * i - 2] = nxt_up(b[i]); a[2 * i - 1] = nxt_up(1); } else { a[2 * i - 2] = nxt_up(1); a[2 * i - 1] = nxt_up(1); } continue; } if (b[i] > b[i - 1]) { if (s.count(b[i])) { a[2 * i - 2] = nxt_down(b[i]); a[2 * i - 1] = nxt_down(2 * n - 1); } else { a[2 * i - 2] = nxt_down(2 * n - 1); a[2 * i - 1] = nxt_down(2 * n - 1); } continue; } assert(0); } for (int i = 1; i <= 2 * n - 1; i++) { cout << a[i] << " "; } cout << "\n"; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 328 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 324 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 1 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 328 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 1 ms | 460 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 460 KB | Output is correct |
2 | Correct | 3 ms | 724 KB | Output is correct |
3 | Correct | 7 ms | 1236 KB | Output is correct |
4 | Correct | 11 ms | 2212 KB | Output is correct |
5 | Correct | 25 ms | 4308 KB | Output is correct |
6 | Correct | 62 ms | 8200 KB | Output is correct |
7 | Correct | 84 ms | 12748 KB | Output is correct |