Submission #42482

#	Time	Username	Problem	Language	Result	Execution time	Memory
42482		Hassoony	medians (balkan11_medians)	C++14	100 / 100	158 ms	15540 KiB

medians

#include<bits/stdc++.h>
#include<unordered_map>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double D;
const ll inf=(1ll<<61);
const ll mod=1e9+7;
const int MX=2e5+9;
int n,a[MX],b[MX],bit[MX],vis[MX];
void add(int x){
    while(x<MX){
        bit[x]++;
        x+=x&-x;
    }
}
int get(int x){
    int ret=0;
    while(x){
        ret+=bit[x];
        x-=x&-x;
    }
    return ret;
}
set<int>s;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
    }
    for(int i=1;i<=2*n-1;i++)s.insert(i);
    add(b[1]);
    a[1]=b[1];
    s.erase(b[1]);
    vis[b[1]]=1;
    int j=2;
    for(int i=2;i<=n;i++){
        if(!vis[b[i]]){
            a[j]=b[i];
            add(b[i]);
            s.erase(b[i]);
            int x=get(b[i]-1);
            int y=get(MX)-get(b[i]);
            if(x>y){
                a[j+1]=*s.rbegin();s.erase(a[j+1]);
            }
            else a[j+1]=*s.begin();s.erase(a[j+1]);
            add(a[j+1]);
            vis[a[j]]=vis[a[j+1]]=1;
            j+=2;
            continue;
        }
        int x=get(b[i]-1);
        int y=get(MX)-get(b[i]);
        if(x==y){
            a[j]=*s.begin();s.erase(s.begin());
            add(a[j]);
            a[j+1]=*s.rbegin();s.erase(a[j+1]);
            add(a[j+1]);
            j+=2;
        }
        else if(x>y){
            a[j]=*s.rbegin();s.erase(a[j]);
            add(a[j]);
            a[j+1]=*s.rbegin();s.erase(a[j+1]);
            add(a[j+1]);
            j+=2;
        }
        else{
            a[j]=*s.begin();s.erase(s.begin());
            add(a[j]);
            a[j+1]=*s.begin();s.erase(s.begin());
            add(a[j+1]);
            j+=2;
        }
        vis[a[j-1]]=vis[a[j-2]]=1;
    }
    for(int i=1;i<=2*n-1;i++)cout<<a[i]<<" ";
}

Compilation message (stderr)

medians.cpp: In function 'int main()':
medians.cpp:30:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&b[i]);
                          ^

• Subtask 1: 65 / 65
• Subtask 2: 35 / 35