Submission #1290680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290680		julia_08	Arranging Shoes (IOI19_shoes)	C++20	30 / 100	27 ms	5448 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using ll = long long;

using namespace std;

const int MAXN = 2e5 + 10;

int bit[MAXN];

vector<int> pos[MAXN][2];

int n;

void bit_add(int pos, int x){
	for(int i=pos; i<=(2 * n); i+=(i&-i)){
		bit[i] += x;
	}
}

int bit_query(int pos){

	int sum = 0;

	for(int i=pos; i>0; i-=(i&-i)){
		sum += bit[i];
	}

	return sum;

}

ll solve(int a){

	if(pos[a][0].empty()) return 0;

	ll ans = 0;

	// cout << pos[a][0].size() << " " << pos[a][1].size() << endl;

	int l = 0, r = 0;

	vector<pair<int, int>> upd;

	while(l < (int) pos[a][0].size()){

		int pos_left = pos[a][0][l], pos_right = pos[a][1][r];

		// cout << "pos " << pos_left << ' ' << pos_right << endl;

		if(pos_left > pos_right){
			swap(pos_left, pos_right);
			ans ++;
		}

		ans += pos_right - pos_left - 1 + (bit_query(pos_right) - bit_query(pos_left));

		bit_add(pos_left, 1);
		bit_add(pos_right, -1);

		upd.push_back({pos_left, -1});
		upd.push_back({pos_right, 1});

		l ++;
		r ++;

	}

	for(auto [pos, x] : upd) bit_add(pos, x);

	return ans;

}

ll count_swaps(vector<int> s){

	n = (int) s.size() / 2;

	for(int i=0; i<(2 * n); i++){
		if(s[i] < 0){
			pos[-s[i]][0].push_back(i + 1);
		} else pos[s[i]][1].push_back(i + 1);
	}

	ll ans = 0;

	for(int i=1; i<=n; i++) ans += solve(i);

	return ans;

}

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