Submission #314511

#	Time	Username	Problem	Language	Result	Execution time	Memory
314511		jaaguptamme	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	10 ms	12800 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=400005;
vector<ll>ar(N,0);
ll get(int p){
    ll ans=0;
    while(p){
        ans+=ar[p];
        p-=p&(-p);
    }
    return ans;
}
void add(int p,ll val){
    while(p<N){
        ar[p]+=val;
        p+=p&(-p);
    }
}
long long count_swaps(std::vector<int> s) {
    vector<pair<int,int>>g[N];
    int n=s.size()/2;
    for(int i=1;i<=2*n;i++){
        int ps=i-1;
        g[abs(s[ps])].push_back({s[ps],i});
        add(i,1);
    }
    ll ans=0;
    vector<pair<int,int>>ns;
    for(int i=1;i<N;i++){
        sort(g[i].begin(),g[i].end());
        int cnt=g[i].size()/2;
        for(int j=0;j<cnt;j++){
            int l=g[i][j].second;
            int r=g[i][j+cnt].second;
            if(l>r){
                ans++;
                swap(l,r);
            }
            ns.push_back({l,r});
        }
    }
    for(auto el:ns){
        int l=el.first,r=el.second;
        ans+=get(r-1)+get(l);
        add(l,-1);add(r,-1);
    }
	return ans;
}

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