# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
145486 | MKopchev | medians (balkan11_medians) | C++14 | 1091 ms | 10104 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |