제출 #377064

#제출 시각아이디문제언어결과실행 시간메모리
377064iliccmarko중앙값 배열 (balkan11_medians)C++14
100 / 100
42 ms3688 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define endl "\n" #define INF 1000000000 #define LINF 1000000000000000LL #define pb push_back #define all(x) x.begin(), x.end() #define len(s) (int)s.size() #define test_case { int t; cin>>t; while(t--)solve(); } #define input(n, v) {for(int i = 0;i<n;i++) cin>>v[i];} #define output(n, v) {for(int i = 0;i<n;i++) cout<<v[i]<<" "; cout<<endl;} #define single_case solve(); #define line cout<<"------------"<<endl; #define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); } const int N = 2e5 + 50; vector<int> a; int b[N]; int n; int c[N]; int l, r; int main() { ios cin>>n; for(int i = 1;i<=n;i++) cin>>b[i]; a.pb(b[1]); c[b[1]]++; int l = 1; int r = 2*n-1; for(int i = 2;i<=n;i++) { while(c[l])l++; while(c[r])r--; if(b[i]==b[i-1]) { a.pb(l); c[l]++; a.pb(r); c[r]++; } else { if(c[b[i]]) { if(b[i]>b[i-1]) { a.pb(r); c[r]++; r--; while(c[r])r--; a.pb(r); c[r]++; r--; } else { a.pb(l); c[l]++; l++; while(c[l])l++; a.pb(l); c[l]++; l++; } } else { a.pb(b[i]); c[b[i]]++; if(b[i]>b[i-1]) { while(c[r])r--; a.pb(r); c[r]++; } else { while(c[l])l++; a.pb(l); l++; } } } } for(int x : a) cout<<x<<" "; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...