제출 #1025353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1025353		LeaRouse	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	126 ms	141440 KiB

shoes

#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;
    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;
        //asignamos pares
        int b=q[d/2-s[i]].front();
        q[d/2-s[i]].pop();  q[d/2+s[i]].pop();

        if(s[i]>0){
            P[i]=a+1;
            P[b]=a;
        }
        else{
            P[i]=a;
            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