Submission #1067872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067872		LittleOrange	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1070 ms	3532 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;
	ll ans = n*n*10;
	vector<ll> p(n*2);
	iota(p.begin(),p.end(),0);
	do{
		ll ok = 1;
		for(ll i = 0;i<n;i++){
			if (s[p[i*2]]>0||s[p[i*2+1]]<0||s[p[i*2]]+s[p[i*2+1]]!=0) {
				ok = 0;
				break;
			}
		}
		if(ok){
			ans = min(ans,invc(p));
		}
	}while(next_permutation(p.begin(),p.end()));
	return ans;
}

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