Submission #152342

#	Time	Username	Problem	Language	Result	Execution time	Memory
152342		xDWaffle	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	96 ms	11960 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define pb push_back
#define ff(j, a, b) for(int j=a;j<b;j++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pint;
const int MAXN = 200005;

struct bit{
	int tree[MAXN];
	void add(int x, int v){
		for(int i=x; i<MAXN; i+=i&-i) tree[i] += v;
	}
	int query(int x){
		int ret = 0;
		for(int i=x; i; i-=i&-i) ret += tree[i];
		return ret;
	}
}bit;


ll count_swaps(vector<int> s) {
	int n = s.size() / 2;
	ll ret = 0;
	vector<pint> v;
	vector<pint> ord[MAXN];
	ff(i, 0, 2*n)
    {
		ord[abs(s[i])].pb(pint(s[i], i));
	}
	ff(i, 1, n+1)
	{
		sort(ord[i].begin(), ord[i].end());
		for(int j=0; j<sz(ord[i])/2; j++){
			int l = ord[i][j].second;
			int r = ord[i][j + ord[i].size()/2].second;
			if(l > r){
				swap(l, r);
				ret++;
			}
			v.pb(pint(l + 1, r + 1));
		}
	}
	ff(i, 1, 2*n+1) bit.add(i, 1);
	sort(v.begin(), v.end());
	for(auto &i : v){
		ret += bit.query(i.second - 1) - bit.query(i.first);
		bit.add(i.first, -1);
		bit.add(i.second, -1);
	}
	return ret;
}

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