Submission #594502

#	Time	Username	Problem	Language	Result	Execution time	Memory
594502		Clan328	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	2 ms	468 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) {
	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)-1;
	}

	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 < n; i++) {
		if (pos[i] < i || S[i] > 0 || dist[i] <= 0) continue;
		res1 += tree.get(1, 0, n-1, pos[i]);
		tree.update(1, 0, n-1, pos[i]+1, n-1, -1);
		
		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 = 0; i < n; i++) cout << nxt[i] << " ";
	// 	cout << 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<int, vi> toRight(int n, vi S) {
	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]);
	}

	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 = n-1; i >= 0; i--) {
		if (pos[i] > i || S[i] > 0) continue;
		res1 += tree.get(1, 0, n-1, pos[i]);
		tree.update(1, 0, n-1, 0, pos[i]-1, -1);

		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;
	}
	// S = newS;

	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);
	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;
			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 right
	vi tmpS = S;
	pair<int, vi> tmp = toRight(n, tmpS);
	tmpS = tmp.second;
	res1 = tmp.first;

	res1 += toLeft(n, tmpS).first;

	// All to left
	tmpS = S;
	tmp = toLeft(n, tmpS);
	tmpS = tmp.second;
	res2 = tmp.first;

	res2 += toRight(n, tmpS).first;

	return min(res1, res2);
}

Compilation message (stderr)

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

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