Submission #788675

#	Time	Username	Problem	Language	Result	Execution time	Memory
788675		LeaRouse	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	126 ms	141748 KiB

shoes

//  Ignorant people are the ones who talk the most.   GO TO HUNGARY!
//  Don't stop uploading
#include <bits/stdc++.h>
#include "shoes.h"
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
using namespace std;
const int MAX=2e5+5;
ll P[MAX],bit[MAX],d=0;

void update(int i,int v){
    while(i<=d){
        bit[i]+=v;
        i+=(i&-i);
    }
}

ll query (int i){
    ll ans=0;
    while(i>0){
        ans+=bit[i];
        i-=(i&-i);
    }
    return ans;
}

ll inv(){
    ll ans=0;
    for(int i=0;i<d;i++){
        ans+=query(P[i]);
        update(P[i],1);
    }
    return ans;
}

ll count_swaps(vector<int>s){
    d=s.size(); 
    int a=1;
    vector<queue<int>>q(MAX);
    for(int i=0;i<d;i++){
        q[s[i]+d/2].push(i);
    }
    for(int i=0;i<d;i++){
        if(P[i])    continue;
        if(s[i]>0){
            P[i]=a+1;
            int b=q[d/2 - s[i]].front();
            q[d/2 - s[i]].pop();
            q[d/2 + s[i]].pop();
            P[b]=a;
            a+=2;
        }
        else{
            P[i]=a;
            int b=q[d/2 - s[i]].front();
            q[d/2 - s[i]].pop();
            q[d/2 + s[i]].pop();
            P[b]=a+1;
            a+=2;
        }
    }
    ll res=d*(d-1)/2;
    ll ans=res-inv();
    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