Submission #294662

#	Time	Username	Problem	Language	Result	Execution time	Memory
294662		mode149256	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	100 ms	23476 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vii = vector<vi>;

struct FENWICK {
	int N;
	vi A;
	FENWICK(int n): N(n) {
		A.resize(N + 1, 0);
	}

	void add(int i, int x) {
		for (; i <= N; i += (i) & (-i))
			A[i] += x;
	}

	int get(int i) {
		int ret = 0;
		for (; i > 0; i -= (i) & (-i))
			ret += A[i];
		return ret;
	}
};

ll count_swaps(vi s) {
	ll ats = 0;
	int N = (int)s.size();
	vb done(N, false);
	vi other(N, -1);

	{
		vector<vii> pos(3, vii(N));
		vii ind(3, vi(N, 0));

		for (int i = 0; i < N; ++i)
		{
			int k = (s[i] > 0 ? 1 : 0);
			int d = 1 - k;
			int m = abs(s[i]);

			if (ind[d][m] < (int)pos[d][m].size()) {
				int kit = pos[d][m][ind[d][m]];
				other[i] = kit;
				other[kit] = i;
				ind[d][m]++;
			} else {
				pos[k][m].emplace_back(i);
			}
		}
		// for (auto u : other) printf("%d ", u);
	}

	FENWICK fen(N + 1);

	for (int i = 0; i < N; ++i)
	{
		if (done[i]) continue;

		int ot = other[i];
		assert(i < ot);

		int cn = fen.get(ot) - fen.get(i);

		ats += ot - i - cn - 1;

		if (s[i] > s[other[i]]) ats++;


		done[other[i]] = done[i] = true;
		fen.add(other[i], 1);
	}
	return ats;
}

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