Submission #835181

#	Time	Username	Problem	Language	Result	Execution time	Memory
835181		MadokaMagicaFan	Scales (IOI15_scales)	C++14	56.77 / 100	1 ms	288 KiB

scales

#include "bits/stdc++.h"
#include "scales.h"
using namespace std;
#define pb push_back

#ifndef ONPC
mt19937 rng(time(NULL));
#endif

void init(int T) {
}

int cnt = 0;

void order(vector<int> &a) {
	cnt += 2;
	int x = getLightest(a[0], a[1], a[2]);
	int y = getMedian(a[0], a[1], a[2]);

	a[2] = a[2] + a[1] + a[0] - x - y;
	a[0] = x;
	a[1] = y;
}

void add3(vector<int> &a, int x) {
	++cnt;
	int u = getMedian(a[1], a[2], x);
	if (u == a[2]) {
		a.push_back(x); return;
	}

	if (u == x) {
		a.push_back(x);
		swap(a[2], a[3]);
		return;
	}


	u = getMedian(a[0], a[1], x);
	++cnt;

	a.push_back(x);
	swap(a[2], a[3]);
	swap(a[1], a[2]);
	if (u == a[0]) swap(a[0], a[1]);
}

void add2(vector<int> &a, int x) {
	int u = getMedian(a[0], a[1], x);
	a.push_back(x);

	if (u == a[1]) return;
	swap(a[1], a[2]);
	if (u == x) return;
	swap(a[0], a[1]);
}

vector<int> cmp(vector<int> a, vector<int> b, int it) {
	vector<int> res;
	int z = getNextLightest(a[0], a[1], a[2], b[1]);
	++cnt;
	int p;
	vector<int> u, v;
	if (z == a[1]) {
		if (it == 0) {
			u = {a[0], b[1]};
			v = {a[1], a[2]};
			add2(u, b[0]); add2(v,b[2]);
			for (auto x : v) u.pb(x);
			return u;
		} else {
			u = {b[0], b[1]};
			add2(u, a[0]);
			u.pb(b[2]);
			u.pb(a[1]);
			u.pb(a[2]);
			return u;
		}
	} else if (z == a[2]) {
		if (it == 0) {
			u = {a[0], a[1]};
			v = {b[1], a[2]};
			add2(u, b[0]); add2(v,b[2]);
			for (auto x : v) u.pb(x);
			return u;
		} else {
			u = {b[1], b[2]};
			v = {a[0], a[1], b[0]};
			add2(u, a[2]);
			v.pb(u[0]);
			v.pb(u[1]);
			v.pb(u[2]);
			return v;
		}
	}

	if (it == 0) return cmp(b, a, 1);

	a.pb(b[0]);
	a.pb(b[1]);
	a.pb(b[2]);

	z = getMedian(a[0], a[3], a[5]);
	cnt++;

	if (z == a[0]) {
		res = {a[3], a[4], a[0], a[5], a[1], a[2]};
		return res;
	}

	if (z == a[5]) {
		res = {a[3], a[4], a[5], a[0], a[1], a[2]};
		return res;
	}

	z = getMedian(a[2], a[3], a[4]);
	cnt++;
	if (z == a[2]) {
		swap(a[3], a[2]);
	}
	return a;
}

void orderCoins() {
	int ans[6];
	vector<int> a(6);
	iota(a.begin(), a.end(), 1);
#ifndef ONPC
	shuffle(a.begin(), a.end(), rng);
#endif

	vector<int> c = a;
	vector<int> b;
	b.pb(c.back());
	c.pop_back();
	b.pb(c.back());
	c.pop_back();
	b.pb(c.back());
	c.pop_back();
	order(b); order(c);

	a = cmp(b, c, 0);
	for (int i = 0; i < 6; ++i)
		ans[i] = a[i];
	answer(ans);
	// cout << cnt << endl;
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:10:15: warning: unused parameter 'T' [-Wunused-parameter]
   10 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'std::vector<int> cmp(std::vector<int>, std::vector<int>, int)':
scales.cpp:62:6: warning: unused variable 'p' [-Wunused-variable]
   62 |  int p;
      |      ^

• Subtask 1: 56.770833 / 100