Submission #1068049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068049		LittleOrange	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	358 ms	152136 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct BIT{
	ll n;
	vector<ll> a;
	BIT(ll N):n(N),a(N+1,0){}
	void add(ll i, ll v){
		for(;i<=n;i+=i&-i) a[i] += v;
	}
	ll get(ll i){
		ll x = 0;
		for(;i>0;i-=i&-i) x += a[i];
		return x;
	}
};
ll invc(const vector<ll>& v){
	ll n = v.size();
	BIT t(n);
	ll r = 0;
	for(ll i = 0;i<n;i++){
		r += i-t.get(v[i]+1);
		t.add(v[i]+1,1);
	}
	return r;
}
long long count_swaps(std::vector<int> s) {
	ll n = s.size()/2;
	if (0&&n<=8){
		ll ans = n*n*10;
		vector<pair<ll,ll>> a;
		for(ll i = 0;i<n*2;i++){
			if (s[i]<0) a.push_back({i,s[i]});
		}
		vector<ll> u(n*2,0);
		for(auto &o : a){
			for(ll i = 0;i<n*2;i++){
				if (!u[i]&&s[i]==-o.second){
					o.second = i;
					u[i] = 1;
					break;
				}
			}
			//cerr << o.first << " " << o.second << "\n";
		}
		do{
			vector<ll> p;
			for(auto &o : a){
				p.push_back(o.first);
				p.push_back(o.second);
			}
			ans = min(ans,invc(p));
		}while(next_permutation(a.begin(),a.end()));
		return ans;
	}
	/*
	vector<ll> to(n*2);
	ll il = 0, ir = 1;
	for(ll i = 0;i<n*2;i++){
		if (s[i]<0){
			to[i] = il;
			il+=2;
		}else {
			to[i] = ir;
			ir+=2;
		}
	}
	return invc(to);*/
	map<ll,deque<ll>> mp;
	vector<pair<ll,ll>> v;
	for(ll i = 0;i<n*2;i++){
		if (mp[-s[i]].size()){
			ll g = mp[-s[i]].front();mp[-s[i]].pop_front();
			v.push_back({g,i});
		}else{
			mp[s[i]].push_back(i);
		}
	}
	sort(v.begin(),v.end());
	vector<ll> to;
	for(auto &o : v){
		if (s[o.first]>0){
			swap(o.first,o.second);
		}
		to.push_back(o.first);
		to.push_back(o.second);
	}
	//for(ll i = 0;i<n*2;i++) cerr << to[i] << " \n"[i+1==n*2];
	return invc(to);
}

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