Submission #490764

#	Time	Username	Problem	Language	Result	Execution time	Memory
490764		hoangtung_pro	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	214 ms	280980 KiB

shoes

#include<bits/stdc++.h>

#define bit(s, i) (s & (1<<i))
#define fi first
#define se second
#define pb push_back
#define endl '\n'

using namespace std;

const int N = 1e5 + 5;
const int M = 1;
const int K = 1;
const int inf = 2e9;
const long long Inf = 2e18;
const int mod = 1e9 + 7;

typedef pair < int, int > ii;
typedef long long ll;

int Bit[N], ass[N];
queue < int > pos[N][2];

void Update(int i) {
	for(; i < N; i += (i & -i)) Bit[i] ++; 
}

int Get(int i) {
	int res = 0;
	for(; i > 0; i -= (i & -i)) res += Bit[i];
	return res;
}

long long count_swaps(vector<int> a) {
	int n = a.size() / 2;
	
	for(int i=0;i<=2 * n - 1;++i) {
		int x = a[i];
		
		if(x < 0) pos[abs(x)][0].push(i + 1);
		else pos[abs(x)][1].push(i + 1);
	}

	for(int i=1;i<=n;++i) {
		while(pos[i][0].size()) {
			int le = pos[i][0].front(), ri = pos[i][1].front();
			pos[i][0].pop(), pos[i][1].pop();
			ass[le] = ri;
			ass[ri] = le;
		}
	}

	long long res = 0;
	int cnt = 0, cur = 0;

	for(int i=0;i<=2 * n - 1;++i) if(a[i] < 0) {
		cur ++;
		int le = i + 1, ri = ass[le];
		if(le > ri) {
			res ++;
			swap(le, ri);
		}
		res += le + ri;
		res -= 2 * cur + 2 * cur - 1;

		res -= Get(le) - cnt;
		Update(le), cnt ++;
		res -= Get(ri) - cnt;
		Update(ri), cnt ++;
	}	

	return res;
}

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