제출 #116493

#제출 시각아이디문제언어결과실행 시간메모리
116493Adhyyan1252중앙값 배열 (balkan11_medians)C++11
100 / 100
85 ms12972 KiB
#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; }

컴파일 시 표준 에러 (stderr) 메시지

medians.cpp: In function 'int main()':
medians.cpp:89:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++){
                 ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...