# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
35526 | 2017-11-24T01:34:04 Z | sinhriv | medians (balkan11_medians) | C++14 | 189 ms | 15056 KB |
#include <bits/stdc++.h> using namespace std; const int N = 200010; int n; int a[N]; int b[N]; vector < pair < int, int > > relate; int d(int x){ if(x < 0) return abs(x); return n + n - x; } int getopp(int x){ return x / abs(x); } bool cmp(pair < int, int > x, pair < int, int > y){ if(getopp(x.first) != getopp(y.first)){ return getopp(x.first) < getopp(y.first); } return d(x.first) < d(y.first); } set < int > unused; void solve(int x, int p){ if(x < 0){ x = abs(x); auto it = unused.upper_bound(x); if(it == unused.begin()) relate.emplace_back(-x, p); else { a[p] = *(--it); unused.erase(a[p]); } } else{ auto it = unused.lower_bound(x); if(it == unused.end()) relate.emplace_back(x, p); else{ a[p] = *it; unused.erase(it); } } } int main(){ if(fopen("1.inp", "r")){ freopen("1.inp", "r", stdin); } set < int > used; scanf("%d", &n); for(int i = 1; i <= n; ++i){ scanf("%d", b + i); used.insert(b[i]); if(i != 1) unused.insert(b[i]); } a[1] = b[1]; unused.erase(a[1]); for(int i = 2; i <= n; ++i){ if(b[i] == b[i - 1]){ solve(b[i], i + i - 1); solve(-b[i], i + i - 2); continue; } if(b[i] < b[i - 1]){ if(unused.count(b[i])){ a[i + i - 1] = b[i]; unused.erase(b[i]); } else solve(-b[i], i + i - 1); solve(-b[i], i + i - 2); } else{ if(unused.count(b[i])){ a[i + i - 1] = b[i]; unused.erase(b[i]); } else solve(b[i], i + i - 1); solve(b[i], i + i - 2); } } set < int > fre; for(int i = 1; i < n + n; ++i){ if(used.count(i) == 0) fre.insert(i); } sort(relate.begin(), relate.end(), cmp); for(auto p : relate){ if(p.first < 0){ a[p.second] = *fre.begin(); fre.erase(fre.begin()); } else{ a[p.second] = *fre.rbegin(); fre.erase(a[p.second]); } } for(int i = 1; i < n + n; ++i){ assert(a[i] != 0); printf("%d ", a[i]); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 3584 KB | Output isn't correct |
2 | Incorrect | 0 ms | 3584 KB | Output isn't correct |
3 | Incorrect | 0 ms | 3584 KB | Output isn't correct |
4 | Incorrect | 0 ms | 3584 KB | Output isn't correct |
5 | Incorrect | 0 ms | 3584 KB | Output isn't correct |
6 | Correct | 0 ms | 3584 KB | Output is correct |
7 | Incorrect | 0 ms | 3584 KB | Output isn't correct |
8 | Incorrect | 0 ms | 3584 KB | Output isn't correct |
9 | Incorrect | 0 ms | 3584 KB | Output isn't correct |
10 | Incorrect | 0 ms | 3584 KB | Output isn't correct |
11 | Incorrect | 0 ms | 3584 KB | Output isn't correct |
12 | Incorrect | 0 ms | 3716 KB | Output isn't correct |
13 | Incorrect | 0 ms | 3716 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 3848 KB | Output isn't correct |
2 | Incorrect | 3 ms | 3980 KB | Output isn't correct |
3 | Incorrect | 9 ms | 4528 KB | Output isn't correct |
4 | Incorrect | 23 ms | 5324 KB | Output isn't correct |
5 | Incorrect | 46 ms | 7068 KB | Output isn't correct |
6 | Incorrect | 93 ms | 10668 KB | Output isn't correct |
7 | Incorrect | 189 ms | 15056 KB | Output isn't correct |