Submission #57791

#	Time	Username	Problem	Language	Result	Execution time	Memory
57791		qkxwsm	Scales (IOI15_scales)	C++17	76.49 / 100	14 ms	1248 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

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}};

//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 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));
		cnt3[1][18][5] = 0;
		//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]]++;
				cnt3[1][j][ret3[i][1][j]]++;
				cnt3[2][j][ret3[i][2][j]]++;
				for (int k = 0; k < 6; k++)
				{
					if (ret[i][j][k] == 6)
					{
						continue;
					}
					cnt[j][k][ret[i][j][k]]++;
				}
			}
		}
		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] * 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] * 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 = randomize(vec.size());
		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)
////		{
////					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 init(int)':
scales.cpp:200:12: warning: conversion to 'unsigned int' from 'time_t {aka long int}' may alter its value [-Wconversion]
  srand(time(0));
        ~~~~^~~
scales.cpp:198:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T)
               ^
scales.cpp: In function 'void orderCoins()':
scales.cpp:327:27: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   int rand_idx = randomize(vec.size());
                  ~~~~~~~~~^~~~~~~~~~~~
scales.cpp:358:7: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
    res--;
    ~~~^~

Subtask 176.488095 / 100

#	Verdict	Execution time	Memory	Grader output
Fetching results...