# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
145482 | MKopchev | medians (balkan11_medians) | C++14 | 131 ms | 12808 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()
{
set<int>::iterator it=active.begin();
int num=*it;
active.erase(it);
return num;
}
int get_back()
{
set<int>::iterator it=active.end();
it--;
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])
{
output[2*i+1]=get_back();
output[2*i]=get_back();
}
else if(inp[i]>inp[i+1])
{
output[2*i+1]=get_front();
output[2*i]=get_front();
}
else
{
output[2*i+1]=get_back();
output[2*i]=get_front();
}
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... |