Submission #594547

#	Time	Username	Problem	Language	Result	Execution time	Memory
594547		Clan328	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	272 ms	36064 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

typedef vector<int> vi;
typedef long long ll;

struct SegmentTree {
	vi a, t;

	SegmentTree(int n, const vi& a) {
		this->a = a;
		t = vi(4*n);
		build(1, 0, n-1);
	}

	void build(int v, int tl, int tr) {
		if (tl == tr) {
			t[v] = a[tl];
		} else {
			int tm = (tl+tr)/2;

			build(2*v, tl, tm);
			build(2*v+1, tm+1, tr);
			t[v] = 0;
		}
	}

	int get(int v, int tl, int tr, int pos) {
		if (tl == tr) return t[v];
		else {
			int tm = (tl+tr)/2;

			if (pos <= tm)
				return t[v] + get(2*v, tl, tm, pos);
			else
				return t[v] + get(2*v+1, tm+1, tr, pos);
		}
	}

	void update(int v, int tl, int tr, int l, int r, int add) {
		if (l > r) return;
		else if (l == tl && r == tr) t[v] += add;
		else {
			int tm = (tl+tr)/2;

			update(2*v, tl, tm, l, min(r, tm), add);
			update(2*v+1, tm+1, tr, max(tm+1, l), r, add);
		}
	}
};

// pair<int, vi> toLeft(int n, vi S, vi especial) {
// 	ll res1 = 0;

// 	vi pos(n);
// 	vi mapper(n+1, -1);
// 	for (int i = 0; i < n; i++) {
// 		int v = abs(S[i]);
// 		if (mapper[v] != -1) {
// 			pos[i] = mapper[v];
// 			pos[mapper[v]] = i;
// 		} else {
// 			mapper[v] = i;
// 		}
// 	}

// 	vi dist(n);
// 	for (int i = 0; i < n; i++) {
// 		dist[i] = abs(pos[i]-i) - (!especial[i]);
// 	}

// 	SegmentTree tree(n, dist);
	
// 	vi nxt(n, -1), prev(n, -1);
// 	for (int i = 0; i < n; i++) {
// 		if (i > 0) prev[i] = i-1;
// 		if (i < n-1) nxt[i] = i+1;
// 	}

// 	for (int i = 0; i < 5; i++) {
// 		if (pos[i] < i || S[i] > 0 || tree.get(1, 0, n-1, pos[i]) <= 0) continue;
// 		res1 += tree.get(1, 0, n-1, pos[i]);
// 		tree.update(1, 0, n-1, pos[i]+1, n-1, -1);

// 		if (nxt[i] == pos[i]) continue;
		
// 		int tmp = nxt[i];
// 		if (nxt[i] != -1) prev[nxt[i]] = pos[i];
// 		nxt[i] = pos[i];

// 		if (nxt[pos[i]] != -1) prev[nxt[pos[i]]] = prev[pos[i]];
// 		if (prev[pos[i]] != -1) nxt[prev[pos[i]]] = nxt[pos[i]];

// 		nxt[pos[i]] = tmp;
// 		prev[pos[i]] = i;
// 	}
// 	int zero = 0;
// 	for (int i = 0; i < n; i++) {
// 		if (prev[i] == -1) zero = i;
// 	}

// 	int idx = 0;
// 	vi newS(n);
// 	// cout << res1 << endl;
	
// 	for (int i = zero; ; i = nxt[i]) {
// 		newS[idx] = S[i];
// 		idx++;
// 		if (nxt[i] == -1) break;
// 	}
// 	S = newS;

// 	return {max(0LL, res1), newS};
// }

pair<ll, vi> toLeft(int n, vi S, vi especial) {
	ll res1 = 0;

	vi pos(n);
	vi mapper(n+1, -1);
	for (int i = 0; i < n; i++) {
		int v = abs(S[i]);
		if (mapper[v] != -1) {
			pos[i] = mapper[v];
			pos[mapper[v]] = i;
		} else {
			mapper[v] = i;
		}
	}

	vi dist(n);
	for (int i = 0; i < n; i++) {
		dist[i] = abs(i-pos[i])-(!especial[i]);
	}

	SegmentTree tree1(n, dist), tree2(n, dist);
	
	vi nxt(n, -1), prev(n, -1);
	for (int i = 0; i < n; i++) {
		if (i > 0) prev[i] = i-1;
		if (i < n-1) nxt[i] = i+1;
	}
	
	for (int i = 0; i < n; i++) {
		int d = (tree1.get(1, 0, n-1, i)+tree2.get(1, 0, n-1, pos[i]))-dist[i];
		if (pos[i] < i || S[i] > 0 || d <= 0) continue;
		// cout << res1 << endl;
		res1 += d;
		tree1.update(1, 0, n-1, i+1, pos[i]-1, -1);
		tree2.update(1, 0, n-1, i+1, pos[i]-1, +1);

		if (nxt[i] == pos[i]) continue;
		int tmp = nxt[i];
		if (nxt[i] != -1) prev[nxt[i]] = pos[i];
		nxt[i] = pos[i];

		if (nxt[pos[i]] != -1) prev[nxt[pos[i]]] = prev[pos[i]];
		if (prev[pos[i]] != -1) nxt[prev[pos[i]]] = nxt[pos[i]];

		nxt[pos[i]] = tmp;
		prev[pos[i]] = i;
	}
	int zero = 0;
	for (int i = 0; i < n; i++) {
		if (prev[i] == -1) zero = i;
	}

	int idx = 0;
	vi newS(n);
	for (int i = zero; ; i = nxt[i]) {
		newS[idx] = S[i];
		idx++;
		if (nxt[i] == -1) break;
	}

	return {max(0LL, res1), newS};
}

pair<ll, vi> toRight(int n, vi S, vi especial) {
	ll res1 = 0;

	vi pos(n);
	vi mapper(n+1, -1);
	for (int i = 0; i < n; i++) {
		int v = abs(S[i]);
		if (mapper[v] != -1) {
			pos[i] = mapper[v];
			pos[mapper[v]] = i;
		} else {
			mapper[v] = i;
		}
	}

	vi dist(n);
	for (int i = 0; i < n; i++) {
		dist[i] = abs(i-pos[i])-(!especial[i]);
	}

	SegmentTree tree1(n, dist), tree2(n, dist);
	
	vi nxt(n, -1), prev(n, -1);
	for (int i = 0; i < n; i++) {
		if (i > 0) prev[i] = i-1;
		if (i < n-1) nxt[i] = i+1;
	}
	
	for (int i = n-1; i >= 0; i--) {
		int d = (tree1.get(1, 0, n-1, i)+tree2.get(1, 0, n-1, pos[i]))-dist[i];
		if (pos[i] > i || S[i] > 0 || d <= 0) continue;
		
		res1 += d;
		tree1.update(1, 0, n-1, pos[i]+1, i-1, -1);
		tree2.update(1, 0, n-1, pos[i]+1, i-1, +1);

		if (nxt[i] == pos[i]) continue;
		int tmp = nxt[i];
		if (nxt[i] != -1) prev[nxt[i]] = pos[i];
		nxt[i] = pos[i];

		if (nxt[pos[i]] != -1) prev[nxt[pos[i]]] = prev[pos[i]];
		if (prev[pos[i]] != -1) nxt[prev[pos[i]]] = nxt[pos[i]];

		nxt[pos[i]] = tmp;
		prev[pos[i]] = i;
	}
	int zero = 0;
	for (int i = 0; i < n; i++) {
		if (prev[i] == -1) zero = i;
	}

	int idx = 0;
	vi newS(n);
	for (int i = zero; ; i = nxt[i]) {
		newS[idx] = S[i];
		idx++;
		if (nxt[i] == -1) break;
	}

	return {max(0LL, res1), newS};
}

ll count_swaps(vi S) {
	int n = S.size();
	vector<pair<vi, vi>> mapper(n+1, pair<vi, vi>());
	for (int i = 0; i < n; i++) {
		int v = abs(S[i]);
		if (S[i] < 0) {
			mapper[v].first.pb(i);
		} else
			mapper[v].second.pb(i);
	}

	int idx = 1;
	vi pos(n), especial(n);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < mapper[i].first.size(); j++) {
			S[mapper[i].first[j]] = -idx;
			S[mapper[i].second[j]] = idx;
			if (mapper[i].first[j] > mapper[i].second[j]) {
				especial[mapper[i].first[j]] = especial[mapper[i].second[j]] = true;
				S[mapper[i].first[j]] = -S[mapper[i].first[j]];
				S[mapper[i].second[j]] = -S[mapper[i].second[j]];
			}
			pos[mapper[i].first[j]] = mapper[i].second[j];
			pos[mapper[i].second[j]] = mapper[i].first[j];
			idx++;
		}
	}

	// for (int i = 0; i < n; i++) cout << S[i] << " ";
	// 	cout << endl;

	ll res1 = 0, res2 = 0;

	// All to left
	pair<ll, vi> tmp = toLeft(n, S, especial);
	res1 = tmp.first;

	for (int i = 0;i < n; i++) S[i] = -S[i];

	// All to right
	tmp = toRight(n, S, especial);
	res2 = tmp.first;
	
	return min(res1, res2);
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(vi)':
shoes.cpp:259:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  259 |   for (int j = 0; j < mapper[i].first.size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~

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