Submission #1250805

#TimeUsernameProblemLanguageResultExecution timeMemory
1250805tradzmedians (balkan11_medians)C++20
100 / 100
77 ms16196 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 7; int n, b[N], a[N]; int bit[N]; void up(int x) { for (; x <= 300000; x += x& - x) bit[x] += 1; } int get(int x) { int ans = 0; for (; x > 0; x -= x& - x) ans += bit[x]; return ans; } int main() { ios_base::sync_with_stdio(0); cin >> n; memset(bit, 0, sizeof bit); for (int i = 1; i <= n; i++) cin >> b[i]; set <int> s; for (int i = 1; i <= 2 * n - 1; i++) s.insert(i); a[1] = b[1]; s.erase(a[1]); up(a[1]); int j = 2; for (int i = 2; i <= n; i++) { int small = get(b[i] - 1); int large = get(2 * n - 1) - get(b[i]); int balance = i - 1; if (s.find(b[i]) != s.end()) { up(b[i]); s.erase(b[i]); a[j] = b[i]; j++; } while (small < balance) { a[j] = *s.begin(); up(a[j]); s.erase(a[j]); j++; small++; } while (large < balance) { a[j] = *s.rbegin(); up(a[j]); s.erase(a[j]); j++; large++; } } for (int i = 1; i <= n * 2 - 1; i++) cout << a[i] << " "; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...