Submission #58063

#	Time	Username	Problem	Language	Result	Execution time	Memory
58063		qkxwsm	Scales (IOI15_scales)	C++17	Compilation error	0 ms	0 KiB

scales

//#include "scales.h"
#include <bits/stdc++.h>

using namespace std;

template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
long long randomize(long long mod)
{
	return ((1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}

#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << endl;

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-20;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll

long long normalize(long long x, long long mod = INF)
{
	return (((x % mod) + mod) % mod);
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

//bad stuff

#define _MAXN 6
#define _MAX_ANSWER_CALLS 1
static int _ind[_MAXN];
static int _numQueries;
int bads = 0;

void answer(int W[]) {
	//	cout << _numQueries << " queries:";
	//	for (int i = 0; i < 6; i++)
	//	{
	//		cout << ' ' << W[i];
	//	}
	//	cout << endl;
	//	cout << _numQueries << " OK\n";
	if (_numQueries > 6)
	{
		//		cerr << "hi\n";
		bads++;
	}
	_numQueries = 0;
}

int getMedian(int A, int B, int C) {
	_numQueries++;
	A--; B--; C--;
	if (_ind[B] < _ind[A] && _ind[A] < _ind[C])
		return A + 1;
	if (_ind[C] < _ind[A] && _ind[A] < _ind[B])
		return A + 1;
	if (_ind[A] < _ind[B] && _ind[B] < _ind[C])
		return B + 1;
	if (_ind[C] < _ind[B] && _ind[B] < _ind[A])
		return B + 1;
	return C + 1;
}

int getHeaviest(int A, int B, int C) {
	_numQueries++;
	A--; B--; C--;
	if (_ind[A] > _ind[B] && _ind[A] > _ind[C])
		return A + 1;
	if (_ind[B] > _ind[A] && _ind[B] > _ind[C])
		return B + 1;
	return C + 1;
}

int getLightest(int A, int B, int C) {
	_numQueries++;
	A--; B--; C--;
	if (_ind[A] < _ind[B] && _ind[A] < _ind[C])
		return A + 1;
	if (_ind[B] < _ind[A] && _ind[B] < _ind[C])
		return B + 1;
	return C + 1;
}

int getNextLightest(int A, int B, int C, int D) {
	int allLess = 1;
	_numQueries++;
	A--; B--; C--; D--;
	if (_ind[A] > _ind[D] || _ind[B] > _ind[D] || _ind[C] > _ind[D])
		allLess = 0;
	if (allLess == 1) {
		if (_ind[A] < _ind[B] && _ind[A] < _ind[C])
			return A + 1;
		if (_ind[B] < _ind[A] && _ind[B] < _ind[C])
			return B + 1;
		return C + 1;
	}
	if (_ind[A] > _ind[D]) {
		if ((_ind[A] < _ind[B] || _ind[B] < _ind[D]) && (_ind[A] < _ind[C] || _ind[C] < _ind[D]))
			return A + 1;
	}
	if (_ind[B] > _ind[D]) {
		if ((_ind[B] < _ind[A] || _ind[A] < _ind[D]) && (_ind[B] < _ind[C] || _ind[C] < _ind[D]))
			return B + 1;
	}
	return C + 1;
}

//end bad stuff

int perm[720][6];
bool dead[720];
int ret3[720][3][20], ret[720][20][6];
int choices[20][3] = {{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 2, 6}, {1, 3, 4}, {1, 3, 5}, {1, 3, 6}, {1, 4, 5}, {1, 4, 6}, {1, 5, 6}, {2, 3, 4}, {2, 3, 5}, {2, 3, 6}, {2, 4, 5}, {2, 4, 6}, {2, 5, 6}, {3, 4, 5}, {3, 4, 6}, {3, 5, 6}, {4, 5, 6}};
int badidx[] = {103, 108, 109, 114, 291, 292, 293, 297, 298, 299, 303, 304, 305, 309, 310, 311, 411, 412, 413, 417, 418, 419, 423, 424, 425, 429, 430, 431, 607, 612, 613, 618, 634, 635, 640, 641};
bool badflag[720];

//BEGIN SKETCH

int getmedian(int A, int B, int C, int idx) {
	if (perm[idx][B] < perm[idx][A] && perm[idx][A] < perm[idx][C])
		return A;
	if (perm[idx][C] < perm[idx][A] && perm[idx][A] < perm[idx][B])
		return A;
	if (perm[idx][A] < perm[idx][B] && perm[idx][B] < perm[idx][C])
		return B;
	if (perm[idx][C] < perm[idx][B] && perm[idx][B] < perm[idx][A])
		return B;
	return C;
}

int getheaviest(int A, int B, int C, int idx) {
	if (perm[idx][A] > perm[idx][B] && perm[idx][A] > perm[idx][C])
		return A;
	if (perm[idx][B] > perm[idx][A] && perm[idx][B] > perm[idx][C])
		return B;
	return C;
}

int getlightest(int A, int B, int C, int idx) {
	if (perm[idx][A] < perm[idx][B] && perm[idx][A] < perm[idx][C])
		return A;
	if (perm[idx][B] < perm[idx][A] && perm[idx][B] < perm[idx][C])
		return B;
	return C;
}

int getnextlightest(int A, int B, int C, int D, int idx) {
	int allLess = 1;
	if (D == A || D == B || D == C) return 6;
	if (perm[idx][A] > perm[idx][D] || perm[idx][B] > perm[idx][D] || perm[idx][C] > perm[idx][D])
		allLess = 0;
	if (allLess == 1) {
		if (perm[idx][A] < perm[idx][B] && perm[idx][A] < perm[idx][C])
			return A;
		if (perm[idx][B] < perm[idx][A] && perm[idx][B] < perm[idx][C])
			return B;
		return C;
	}
	if (perm[idx][A] > perm[idx][D]) {
		if ((perm[idx][A] < perm[idx][B] || perm[idx][B] < perm[idx][D]) && (perm[idx][A] < perm[idx][C] || perm[idx][C] < perm[idx][D]))
			return A;
	}
	if (perm[idx][B] > perm[idx][D]) {
		if ((perm[idx][B] < perm[idx][A] || perm[idx][A] < perm[idx][D]) && (perm[idx][B] < perm[idx][C] || perm[idx][C] < perm[idx][D]))
			return B;
	}
	return C;
}

//END SKETCH
vector<int> v;
int ans[6], ansidx;

void init(int T)
{
	srand(time(0));
	for (int x : badidx)
	{
		badflag[x] = true;
	}
	for (int i = 0; i < 6; i++)
	{
		perm[0][i] = i;
	}
	for (int i = 0; i < 20; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			choices[i][j]--;
		}
	}
	for (int i = 1; i < 720; i++)
	{
		for (int j = 0; j < 6; j++)
		{
			perm[i][j] = perm[i - 1][j];
		}
		next_permutation(perm[i], perm[i] + 6);
	}
	//	cerr << getmedian(3, 4, 5, 1) << endl;
	for (int i = 0; i < 720; i++)
	{
		for (int j = 0; j < 20; j++)
		{
			ret3[i][0][j] = getmedian(choices[j][0], choices[j][1], choices[j][2], i);
			ret3[i][1][j] = getheaviest(choices[j][0], choices[j][1], choices[j][2], i);
			ret3[i][2][j] = getlightest(choices[j][0], choices[j][1], choices[j][2], i);
			for (int k = 0; k < 6; k++)
			{
				ret[i][j][k] = getnextlightest(choices[j][0], choices[j][1], choices[j][2], k, i);
			}
			//			cout << ret3[i][0][j] << endl;
		}
	}
}

void orderCoins()
{
	for (int i = 0; i < 6; i++)
	{
		ans[i] = i;
	}
	for (int i = 0; i < 720; i++)
	{
		dead[i] = false;
	}
	//	cerr << "hi\n";
	while(true)
	{
		int cnt3[3][20][6], cnt[20][6][6];
		memset(cnt3, 0, sizeof(cnt3));
		memset(cnt, 0, sizeof(cnt));
		//life is too short for some things...
		for (int i = 0; i < 720; i++)
		{
			if (dead[i])
			{
				continue;
			}
			for (int j = 0; j < 20; j++)
			{
				cnt3[0][j][ret3[i][0][j]] += 2;
				cnt3[1][j][ret3[i][1][j]] += 2;
				cnt3[2][j][ret3[i][2][j]] += 2;
				if (badflag[i])
				{
					cnt3[0][j][ret3[i][0][j]] += 1;
					cnt3[1][j][ret3[i][1][j]] += 1;
					cnt3[2][j][ret3[i][2][j]] += 1;
				}
				for (int k = 0; k < 6; k++)
				{
					if (ret[i][j][k] == 6)
					{
						continue;
					}
					cnt[j][k][ret[i][j][k]] += 2;
					if (badflag[i])
					{
						cnt[j][k][ret[i][j][k]] += 1;
					}
				}
			}
		}
		ll best = LLINF;
		bool flag; int x, y;
		vector<pair<bool, pii> > vec;
		for (int i = 0; i < 3; i++)
		{
			for (int j = 0; j < 20; j++)
			{
				ll cur = 0;
				for (int k = 0; k < 6; k++)
				{
					cur += 1ll * cnt3[i][j][k] * cnt3[i][j][k];
					//					ckmax(cur, cnt3[i][j][k]);
				}
				//				cerr << cur << ' ' << i << ' '<< j << endl;
				if (cur < best)
				{
					best = cur;
					vec.clear();
					vec.PB(MP(false, MP(i, j)));
					//					flag = false; x = i; y = j;
				}
				else if (cur == best)
				{
					vec.PB(MP(false, MP(i, j)));
				}
			}
		}
		for (int i = 0; i < 20; i++)
		{
			for (int j = 0; j < 6; j++)
			{
				if (ret[0][i][j] == 6) continue;
				ll cur = 0;
				for (int k = 0; k < 6; k++)
				{
					cur += 1ll * cnt[i][j][k] * cnt[i][j][k];
					//					ckmax(cur, cnt[i][j][k]);
				}
				if (cur < best)
				{
					best = cur;
					vec.clear();
					vec.PB(MP(true, MP(i, j)));
					//					flag = true; x = i; y = j;
				}
				else if (cur == best)
				{
					vec.PB(MP(true, MP(i, j)));
				}
			}
		}
		int rand_idx = 0;
		flag = vec[rand_idx].fi; x = vec[rand_idx].se.fi; y = vec[rand_idx].se.se;
		//		debug(best); debug(flag); debug(x); debug(y);
		int res;
		if (flag)
		{
			res = getNextLightest(choices[x][0] + 1, choices[x][1] + 1, choices[x][2] + 1, y + 1);
			res--;
			for (int i = 0; i < 720; i++)
			{
				if (ret[i][x][y] != res)
				{
					dead[i] = true;
				}
			}
		}
		else
		{
			if (x == 0)
			{
				res = getMedian(choices[y][0] + 1, choices[y][1] + 1, choices[y][2] + 1);
			}
			if (x == 1)
			{
				res = getHeaviest(choices[y][0] + 1, choices[y][1] + 1, choices[y][2] + 1);
			}
			if (x == 2)
			{
				res = getLightest(choices[y][0] + 1, choices[y][1] + 1, choices[y][2] + 1);
			}
			res--;
			for (int i = 0; i < 720; i++)
			{
				if (ret3[i][x][y] != res)
				{
					dead[i] = true;
				}
			}
		}
		int alives = 0;
		for (int i = 0; i < 720; i++)
		{
			if (!dead[i])
			{
				alives++;
				ansidx = i;
			}
		}
		if (alives == 1)
		{
			break;
		}
	}
	for (int i = 0; i < 6; i++)
	{
		ans[perm[ansidx][i]] = i + 1;
	}
	//all 90 possible moves...
	//getMedian, getHeaviest, getLightest, getNextLightest
	answer(ans);
}

int main()
{
	int T;
	//	cin >> T;
	T = 720;
	init(T);
	for (int tc = 0; tc < T; tc++)
	{
		for (int i = 0; i < 6; i++)
		{
			_ind[i] = i;
		}
		for (int i = 0; i < tc; i++)
		{
			next_permutation(_ind, _ind + 6);
		}
		int wasbads = bads;
		orderCoins();
		int nowbads = bads;
//		if (wasbads != nowbads)
//		{
//			cerr << tc << ", ";
			//					for (int i = 0; i < 6; i++)
			//					{
			//						cerr << _ind[i] << ' ';
			//					}
			//					cerr << endl;
//		}
		//		orderCoins();
	}
	debug(bads);
}

Compilation message (stderr)

In file included from grader.c:2:0:
graderlib.c: In function 'void answer(int*)':
graderlib.c:53:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (_ghksjhdfkae19ga_ > 1) 
     ^~
graderlib.c:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  for (i = 0; i < 6; i++) {
  ^~~
scales.cpp: In function 'void answer(int*)':
scales.cpp:60:19: warning: unused parameter 'W' [-Wunused-parameter]
 void answer(int W[]) {
                   ^
scales.cpp: In function 'void init(int)':
scales.cpp:202:12: warning: conversion to 'unsigned int' from 'time_t {aka long int}' may alter its value [-Wconversion]
  srand(time(0));
        ~~~~^~~
scales.cpp:200:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T)
               ^
scales.cpp: In function 'int main()':
scales.cpp:420:7: warning: unused variable 'wasbads' [-Wunused-variable]
   int wasbads = bads;
       ^~~~~~~
scales.cpp:422:7: warning: unused variable 'nowbads' [-Wunused-variable]
   int nowbads = bads;
       ^~~~~~~
scales.cpp: In function 'void orderCoins()':
scales.cpp:372:7: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
    res--;
    ~~~^~
/tmp/ccFgzoSu.o: In function `main':
scales.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccgpoSqg.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccgpoSqg.o: In function `main':
grader.c:(.text.startup+0x76): undefined reference to `init'
grader.c:(.text.startup+0xe1): undefined reference to `orderCoins'
collect2: error: ld returned 1 exit status