Submission #440613

#	Time	Username	Problem	Language	Result	Execution time	Memory
440613		julian33	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	283 ms	276164 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}

const int mxN=2e5+5;

int bit[mxN];
queue<int> pos[mxN],neg[mxN];
vector<pii> prs;

void upd(int x){while(x<mxN){bit[x]++;x+=x&-x;}}
int sum(int x){int res=0;while(x){res+=bit[x];x-=x&-x;}return res;}

long long count_swaps(std::vector<int> S){
    int n=sz(S);
    int cur=0;
    vector<int> go(n),p(n);
    for(int i=0;i<n;i++){
        int val=abs(S[i]);
        if(S[i]<0){
            if(sz(pos[val])){
                prs.pb(minmax({i,pos[val].front()}));
                pos[val].pop();
            } else{
                neg[val].push(i);
            }
        } else{
            if(sz(neg[val])){
                prs.pb(minmax({neg[val].front(),i}));
                neg[val].pop();
            } else{
                pos[val].push(i);
            }
        }
        p[i]=i;
    }
    sort(prs.begin(),prs.end());
    for(pii &i:prs){
        go[i.first]=cur++;
        go[i.second]=cur++;
        if(S[i.first]>0){
            swap(go[i.first],go[i.second]);
        }
    }
    ll ans=0;
    sort(p.begin(),p.end(),[&](int x,int y){return go[x]<go[y];});
    for(int &i:p){
        ans+=sum(n)-sum(i);
        upd(i+1);
        assert(ans>=0);
    }
    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