Submission #145486

#TimeUsernameProblemLanguageResultExecution timeMemory
145486MKopchevmedians (balkan11_medians)C++14
70 / 100
1091 ms10104 KiB
#include<bits/stdc++.h> using namespace std; const int nmax=2e5+42; int n,inp[nmax]; int output[nmax]; set<int> active; map<int,int> seen; int get_front(int now) { set<int>::iterator it=lower_bound(active.begin(),active.end(),now); it--; int num=*it; active.erase(it); return num; } int get_back(int now) { set<int>::iterator it=lower_bound(active.begin(),active.end(),now); int num=*it; active.erase(it); return num; } int main() { scanf("%i",&n); for(int i=1;i<=n;i++) scanf("%i",&inp[i]); for(int i=1;i<=2*n-1;i++) active.insert(i); output[1]=inp[1]; for(int i=1;i<n;i++) { seen[inp[i]]++; active.erase(inp[i]); } for(int i=n-1;i>=1;i--) { if(inp[i]<inp[i+1]) { set<int>::iterator it=lower_bound(active.begin(),active.end(),inp[i]); int num=*it; it++; int num_2=*it; output[2*i+1]=num; output[2*i]=num_2; active.erase(num); active.erase(num_2); } else if(inp[i]>inp[i+1]) { set<int>::iterator it=lower_bound(active.begin(),active.end(),inp[i]); it--; int num=*it; it--; int num_2=*it; output[2*i+1]=num; output[2*i]=num_2; active.erase(num); active.erase(num_2); } else { output[2*i+1]=get_back(inp[i]); output[2*i]=get_front(inp[i]); } seen[inp[i]]--; if(seen[inp[i]]==0) active.insert(inp[i]); } for(int i=1;i<=2*n-1;i++) printf("%i ",output[i]); return 0; }

Compilation message (stderr)

medians.cpp: In function 'int main()':
medians.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
medians.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&inp[i]);
         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...