Submission #1232836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232836		coco2311	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	129 ms	144668 KiB

shoes

#include "shoes.h"
#include <cmath>
#include <queue> 
#include <cstdio>
using namespace std;

int zp;

long long count_swaps(std::vector<int> s){
	long long N=s.size();
	N/=2;
    zp=1<<(int)ceil(log2(N*2));
    long long arb[2*zp];
    for(int i=0;i<2*zp;i++){
        arb[i]=0;
    }
    long long shoes[2*N];
    for(int i=0;i<2*N;i++){
        shoes[i]=s[i];
        shoes[i]+=N;
    }
    queue<long long> pairD[2*N+1];
    long long pP[2*N+1];
    for(int i=0;i<N*2;i++){
        long long p=shoes[i];
        p-=N;
        p*=-1;
        p+=N;
        if(!pairD[p].empty()){
            pP[i]=pairD[p].front();
            pP[pP[i]]=i;
            pairD[p].pop();
        }
        else{
            pairD[shoes[i]].push(i);
        }
    }
    long long swaps=0;
    for(int i=0;i<2*N;i++){
        if(pP[i]>i){
            long long d=pP[i]-i;
            if(shoes[i]<N){
                d--;
            }
            long long l=i+zp,r=pP[i]+zp,val=0;
            while(l<=r){
                if(l%2==1){
                    val+=arb[l];
                    l++;
                }
                if(r%2==0){
                    val+=arb[r];
                    r--;
                }
                l/=2;
                r/=2;
            }
            d-=val;
            swaps+=d;
            l=pP[i]+zp;
            while(l>=1){
                arb[l]+=1;
                l/=2;
            }
        }
    }
    return swaps;
}

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