Submission #520134

#	Time	Username	Problem	Language	Result	Execution time	Memory
520134		A_D	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	237 ms	275132 KiB

shoes

#include "shoes.h"

#include <bits/stdc++.h>
using namespace std;
const int NN=2e5+100;
int bit[2*NN];
bool vis[NN];
deque<int> l[NN];
deque<int> r[NN];
vector<int> a;
void add(int idx,int val)
{
    while(idx<NN){
        bit[idx]+=val;
        idx+=(idx)&(-idx);
    }
}
long long get(int idx)
{
    long long ret=0;
    while(idx>0){
        ret+=bit[idx];
        idx-=idx&(-idx);
    }
    return ret;
}
long long count_swaps(vector<int> s){
    long long ans=0;
    int nn=s.size();
    a.push_back(0);
    for(int i=0;i<nn;i++){
        a.push_back(s[i]);
    }
    for(int i=1;i<=nn;i++){
        add(i,1);
        if(a[i]>0){
            r[a[i]].push_back(i);
        }
        else{
            l[-a[i]].push_back(i);
        }
    }
    for(int i=1;i<=nn;i++){
        if(vis[i])continue;
        vis[i]=1;
        int u=abs(a[i]);
        if(a[i]>0){
            if(r[u].empty())return 0;
            r[u].pop_front();
            ans+=get(l[u].front())-get(i);
            vis[l[u].front()]=1;
            add(l[u].front(),-1);
            if(l[u].empty())return 0;
            l[u].pop_front();
        }
        else{
            if(l[u].empty())return 0;
            l[u].pop_front();
            ans+=get(r[u].front())-get(i)-1;
            add(r[u].front(),-1);
            vis[r[u].front()]=1;
            if(r[u].empty())return 0;
            r[u].pop_front();

        }
    //    cout<<ans<<"\n";
      //  for(int j=1;j<=n;j++)cout<<vis[j]<<" ";cout<<endl;
    }
//    cout<<endl;
    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15