Submission #585125

#TimeUsernameProblemLanguageResultExecution timeMemory
585125Petymedians (balkan11_medians)C++14
100 / 100
96 ms13004 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const int INF = 1e9; const int MOD = 1e9 + 7; int n, a[100002], b[200002], viz[200002]; set<int>s; int main () { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; viz[a[1]] = 1; for (int i = 1; i < 2 * n; i++) s.insert(i); s.erase(a[1]); b[1] = a[1]; for (int i = 2; i <= n; i++) { if (a[i] == a[i - 1]) { b[2 * i - 1] = *s.begin(); b[2 * i - 2] = *prev(s.end()); s.erase(b[2 * i - 1]); s.erase(b[2 * i - 2]); viz[b[2 * i - 2]] = 1; viz[b[2 * i - 1]] = 1; } else if (a[i] > a[i - 1]) { b[2 * i - 1] = *prev(s.end()); s.erase(*prev(s.end())); if (viz[a[i]]) b[2 * i - 2] = *prev(s.end()); else b[2 * i - 2] = a[i]; s.erase(b[2 * i - 2]); viz[b[2 * i - 2]] = 1; viz[b[2 * i - 1]] = 1; } else { b[2 * i - 1] = *s.begin(); auto it = s.begin(); if (viz[a[i]]) { it++; b[2 * i - 2] = *it; } else b[2 * i - 2] = a[i]; s.erase(b[2 * i - 1]); s.erase(b[2 * i - 2]); viz[b[2 * i - 2]] = 1; viz[b[2 * i - 1]] = 1; } } for (int i = 1; i < 2 * n; i++) cout << b[i] << " "; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...