Submission #305509

#	Time	Username	Problem	Language	Result	Execution time	Memory
305509		knon0501	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	355 ms	275184 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int MX=2e5+5;
int nn;
queue<int> a[MX],b[MX];
int bit[MX*2];
int n;
int f(int x){
    int ret=0;
    for(int i=x ; i>=1 ; i-=(i&-i))ret+=bit[i];
    return ret;
}
void upd(int x){
    for(int i=x ; i<=n ; i+=(i&-i))bit[i]++;
}
long long count_swaps(std::vector<int> s) {
    int i,j;
    long long ans=0;
    n=s.size();
    for(i=0 ; i<n ; i++){
        if(s[i]>0)
            a[s[i]].push(i);
        else
            b[-s[i]].push(i);
    }
    vector<pair<int,int>> v;
    for(i=1 ; i*2<=n ; i++){
        while(!a[i].empty()){
            v.push_back({a[i].front(),b[i].front()});
            a[i].pop();
            b[i].pop();
        }
    }
    sort(v.begin(),v.end(),[&](pair<int,int> q,pair<int,int> w){
         return q.first+q.second-(q.first>q.second)>w.first+w.second-(w.first>w.second);
         });

    for(i=0 ; i<n ; i+=2){
        auto k=v.back();
        v.pop_back();
        ans+=k.first+k.second-(k.first>k.second)+f(n)*2-f(k.first+1)-f(k.second+1)-i*2;
        upd(k.first+1);
        upd(k.second+1);
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:18:11: warning: unused variable 'j' [-Wunused-variable]
   18 |     int i,j;
      |           ^

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