Submission #170684

#	Time	Username	Problem	Language	Result	Execution time	Memory
170684		youngyojun	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	98 ms	21204 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define rb(x) ((x)&(-(x)))
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 200055;

struct BIT {
	int d[MAXN];

	void upd(int x, int r) {
		for(x += 5; x < MAXN; x += rb(x))
			d[x] += r;
	}
	int get(int x) {
		int r = 0;
		for(x += 5; x; x -= rb(x))
			r += d[x];
		return r;
	}
} bit;

vector<int> AV[MAXN], BV[MAXN];

int A[MAXN], B[MAXN];
bitset<MAXN> chk;

ll Ans;
int N;

ll solve() {
	for(int i = 0; i < N*2; i++) {
		if(A[i] < 0) AV[-A[i]].eb(i);
		else BV[A[i]].eb(i);
	}
	for(int i = 1; i <= N; i++) {
		reverse(allv(AV[i]));
		reverse(allv(BV[i]));
	}
	for(int i = 0, x, y, cnt = 0; i < N*2; i++) if(!chk[i]) {
		chk[i] = true;
		x = A[i];
		if(x < 0) {
			B[i] = cnt++;
			AV[-x].pop_back();
			y = BV[-x].back();
			BV[-x].pop_back();
			B[y] = cnt++;
			chk[y] = true;
		} else {
			B[i] = cnt+1;
			BV[x].pop_back();
			y = AV[x].back();
			AV[x].pop_back();
			B[y] = cnt;
			cnt += 2;
			chk[y] = true;
		}
	}

	for(int i = N*2; i--;) {
		Ans += bit.get(B[i]);
		bit.upd(B[i], 1);
	}
	return Ans;
}

long long count_swaps(std::vector<int> s) {
	N = sz(s)/2;
	for(int i = 0; i < N*2; i++) A[i] = s[i];
	return solve();
}

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