Submission #725922

#	Time	Username	Problem	Language	Result	Execution time	Memory
725922		alvingogo	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	121 ms	140572 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
using namespace std;
 
struct BIT{
	int n;
	vector<int> bt;
	void init(int x){
		n=x;
		bt.resize(n+1);
	}
	void update(int x,int y){
		for(;x<=n;x+=(x&-x)){
			bt[x]+=y;
		}
	}
	int query(int x){
		int ans=0;
		for(;x>0;x-=(x&-x)){
			ans+=bt[x];
		}
		return ans;
	}
};
long long count_swaps(vector<int> s) {
	int n=s.size();
	long long ans=1e18;
    vector<pair<int,int> > nw;
    int gg=0;
	vector<queue<pair<int,int> > > cnt(n+1);
	for(int i=0;i<n;i++){
		int u=abs(s[i]);
		if(!cnt[u].size() || cnt[u].front().fs==s[i]){
			cnt[u].push({s[i],i});
		}
		else{
            nw.push_back({cnt[u].front().sc,i});
            if(s[i]<0){
                gg++;
            }
			cnt[u].pop();
		}
	}
    sort(nw.begin(),nw.end());
    vector<int> z(n/2);
    iota(z.begin(),z.end(),0);
    do{
        BIT bt;
        bt.init(n);
        long long nz=0;
        for(int i=0;i<n;i++){
            bt.update(i+1,1);
        }
        for(int i=0;i<n/2;i++){
            bt.update(nw[z[i]].fs+1,-1);
            nz+=bt.query(nw[z[i]].fs+1);
            bt.update(nw[z[i]].sc+1,-1);
            nz+=bt.query(nw[z[i]].sc+1);
        }
        ans=min(ans,nz);
        break;
    }while(next_permutation(z.begin(),z.end()));
    return ans+gg;
}

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