Submission #1101129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101129		rainboy	Treasure (IOI24_treasure)	C++17	100 / 100	288 ms	6136 KiB

treasure

#include "treasure.h"
#include <cstring>
#include <utility>
#include <vector>

using namespace std;

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

namespace encoder {
	const int N = 40000, X = 500000001, A = 2000000001;

	unsigned int Z = 12345;

	int rand_() {
		return (Z *= 3) >> 1;
	}

	int xx[N], yy[N], ii[N], ii_[N], pp[N];

	int *vv;

	void sort(int *ii, int l, int r) {
		while (l < r) {
			int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
			while (j < k)
				if (vv[ii[j]] == vv[i_])
					j++;
				else if (vv[ii[j]] < vv[i_]) {
					tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
					i++, j++;
				} else {
					k--;
					tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
				}
			sort(ii, l, i);
			l = k;
		}
	}

	vi encode(vpi xy) {
		int n = xy.size();
		for (int i = 0; i < n; i++)
			xx[i] = xy[i].first, yy[i] = xy[i].second;
		vi aa(n * 3, A - 1);
		for (int i = 0; i < n; i++)
			aa[i] = xx[i], aa[n + i] = X + yy[i];
		for (int i = 0; i < n; i++)
			ii[i] = i;
		vv = yy, sort(ii, 0, n);
		for (int i = 0; i < n; i++)
			yy[ii[i]] = i;
		vv = xx, sort(ii, 0, n);
		for (int i = 0; i < n; i++) {
			int p = yy[ii[i]];
			ii_[pp[i] = p] = i;
		}
		memcpy(ii, ii_, n * sizeof *ii_);
		for (int j = n - 1; j >= 0; j--) {
			int i = ii[j];
			aa[n * 2 + j] = X * 2 + j * (j + 1) / 2 + i;
			int p = pp[i], q = pp[j];
			ii[pp[i] = q] = i, ii[pp[j] = p] = j;
		}
		return aa;
	}
}

vi encode(vpi xy) {
	return encoder::encode(xy);
}

namespace decoder {
	const int N = 40000, X = 500000001, A = 2000000001;

	unsigned int Z = 12345;

	int rand_() {
		return (Z *= 3) >> 1;
	}

	int xx[N], yy[N], aa[N * 3];

	int *vv;

	void sort(int *aa, int l, int r) {
		while (l < r) {
			int i = l, j = l, k = r, a = aa[l + rand_() % (r - l)], tmp;
			while (j < k)
				if (aa[j] == a)
					j++;
				else if (aa[j] < a) {
					tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
					i++, j++;
				} else {
					k--;
					tmp = aa[j], aa[j] = aa[k], aa[k] = tmp;
				}
			sort(aa, l, i);
			l = k;
		}
	}

	vpi decode(vi aa_) {
		int n = aa_.size() / 3;
		for (int i = 0; i < n * 3; i++)
			aa[i] = aa_[i];
		sort(aa, 0, n * 3);
		for (int i = 0; i < n; i++)
			xx[i] = aa[i], yy[i] = aa[n + i] - X;
		for (int j = 0; j < n; j++) {
			int i = aa[n * 2 + j] - X * 2 - j * (j + 1) / 2, tmp;
			tmp = yy[i], yy[i] = yy[j], yy[j] = tmp;
		}
		vpi xy(n);
		for (int i = 0; i < n; i++)
			xy[i] = make_pair(xx[i], yy[i]);
		return xy;
	}
}

vpi decode(vi aa) {
	return decoder::decode(aa);
}

• Subtask 0: 0 / 0
• Subtask 1: 21 / 21
• Subtask 2: 79 / 79