Submission #1047486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047486		Kel_Mahmut	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	59 ms	15020 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
// #define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

struct fenwick{
	int n;
	vector<int> fen;
	fenwick(int n) : n(n), fen(n){}

	void upd(int pos, int val){
		for(; pos < n; pos |= pos + 1)
			fen[pos] += val;
	}

	int index(int ind){
		int ret = 0;
		for(; ind >= 0; ind = (ind & (ind + 1)) - 1)
			ret += fen[ind];
		return ret;
	}
};

ll count_swaps(vector<int> v){
	int n = v.size() / 2;

	vector<vector<int>> a(n * 2 + 1);
	for(int i = 2 * n - 1; i >= 0; i--){
		a[v[i] + n].pb(i);
	}
	fenwick fen(2 * n);
	for(int i = 0; i < 2 * n; i++){
		fen.upd(i, 1);
	}

	ll ans = 0;
	vector<int> el(2 * n);
	for(int i = 0; i < 2*n; i++){
		while(i < 2 * n && fen.index(i) == 0) i++;
		if(i == 2 * n) break;
		if(v[i] < 0){
			fen.upd(i, -1);
			int nxt = a[-v[i] + n].back(); a[-v[i] + n].pop_back();
			while(el[nxt]){
				nxt = a[-v[i] + n].back(); a[-v[i] + n].pop_back();
			}
			int ind = fen.index(nxt);
			ans += ind - 1;
			fen.upd(nxt, -1);
			el[nxt] = el[i] = 1;
		}
		else{
			int nxt = a[-v[i] + n].back(); a[-v[i] + n].pop_back();
			while(el[nxt]){
				nxt = a[-v[i] + n].back(); a[-v[i] + n].pop_back();
			}
			fen.upd(i, -1);
			int ind = fen.index(nxt);
			ans += ind;
			fen.upd(nxt, -1);
			el[nxt] = el[i] = 1;
		}
	}

	return ans;
}

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