# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
116493 | 2019-06-12T15:41:09 Z | Adhyyan1252 | 중앙값 배열 (balkan11_medians) | C++11 | 85 ms | 12972 KB |
#include<bits/stdc++.h> //https://oj.uz/problem/view/balkan11_mediansxx using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; vector<int> b(n); for(int i = 0; i < n; i++) cin>>b[i]; vector<int> suffMax(n), suffMin(n); suffMax[n-1] = b[n-1]; suffMin[n-1] = b[n-1]; for(int i = n-2; i >= 0; i--){ suffMax[i] = max(suffMax[i+1], b[i]); suffMin[i] = min(suffMin[i+1], b[i]); } vector<int> a(2*n-1); a[0] = b[0]; set<int> s; for(int i = 1; i <= 2*n-1; i++){ if(i == b[0]) continue; s.insert(i); } for(int i = 1; i < n; i++){ if(b[i] > b[i-1]){ if(s.find(b[i]) != s.end()){ // not inserted yet, insert now a[i*2-1] = b[i]; s.erase(b[i]); assert(s.size() > 0); auto it = s.end(); it--; a[i*2] = *it; s.erase(it); }else{ assert(s.size() > 0); auto it = s.end(); it--; a[i*2-1] = *it; s.erase(it); assert(s.size() > 0); it = s.end(); it--; a[i*2] = *it; s.erase(it); } }else if(b[i] < b[i-1]){ if(s.find(b[i]) != s.end()){ // not inserted yet, insert now a[i*2-1] = b[i]; s.erase(b[i]); assert(s.size() > 0); auto it = s.begin(); a[i*2] = *it; s.erase(it); }else{ assert(s.size() > 0); auto it = s.begin(); a[i*2-1] = *it; s.erase(it); assert(s.size() > 0); it = s.begin(); a[i*2] = *it; s.erase(it); } }else if(b[i] == b[i-1]){ assert(s.size() > 0); auto it = s.end(); it--; a[i*2-1] = *it; s.erase(it); assert(s.size() > 0); it = s.begin(); a[i*2] = *it; s.erase(it); }else{ assert(false); } } for(int i = 0; i < a.size(); i++){ cout<<a[i]<<" "; } cout<<endl; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
8 | Correct | 2 ms | 384 KB | Output is correct |
9 | Correct | 2 ms | 384 KB | Output is correct |
10 | Correct | 2 ms | 384 KB | Output is correct |
11 | Correct | 2 ms | 384 KB | Output is correct |
12 | Correct | 2 ms | 384 KB | Output is correct |
13 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 512 KB | Output is correct |
2 | Correct | 4 ms | 896 KB | Output is correct |
3 | Correct | 7 ms | 1408 KB | Output is correct |
4 | Correct | 13 ms | 2304 KB | Output is correct |
5 | Correct | 27 ms | 4472 KB | Output is correct |
6 | Correct | 52 ms | 8440 KB | Output is correct |
7 | Correct | 85 ms | 12972 KB | Output is correct |