Submission #725806

#	Time	Username	Problem	Language	Result	Execution time	Memory
725806		alvingogo	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	40 ms	8904 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;
	}
}bt;
long long count_swaps(vector<int> s) {
	int n=s.size();
	bt.init(n);
	long long ans=0;
	vector<vector<int> > gg(n/2+1);
	vector<pair<int,int> > t;
	for(int i=0;i<n;i++){
		bt.update(i+1,1);
		if(s[i]<0){
			t.push_back({-s[i],i+1});
		}
		else{
			gg[s[i]].push_back(i+1);
		}
	}
	for(auto &h:gg){
		reverse(h.begin(),h.end());
	}
	for(auto z:t){
		bt.update(z.sc,-1);
		ans+=bt.query(z.sc);
		auto y=gg[z.fs].back();
		gg[z.fs].pop_back();
		bt.update(y,-1);
		ans+=bt.query(y);
	}
	return ans;
}

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