Submission #59669

#	Time	Username	Problem	Language	Result	Execution time	Memory
59669		reality	Scales (IOI15_scales)	C++17	72.92 / 100	361 ms	1712 KiB

scales

#include "scales.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
 
//getHeaviest
//getLightest
//getMedian
//getNextLightest
void init(int T) {
	return;
}
/*int dp[1 << 24];
int fr[1 << 24];
const int N = 14348907;
const int p3[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969};
*/
 
map < vi , vi > M;
int was[6666];
void orderCoins() {
	srand(6969);
	M.clear();
	memset(was,0,sizeof(was));
	vi p;
	for (int i = 1;i < 7;++i)
		p.pb(i);
	do {
		vi q(7);
		vi cur;
		for (int i = 0;i < 6;++i)
			q[p[i]] = i + 1;
		for (int i = 1;i <= 6;++i)
			for (int j = i + 1;j <= 6;++j)
				for (int k = j + 1;k <= 6;++k) {
					int mn = min({q[i],q[j],q[k]});
					for (int t = 1;t <= 6;++t)
						if ((t == i || t == j || t == k) && q[t] == mn)
							cur.pb(t);
					int mx = max({q[i],q[j],q[k]});
					for (int t = 1;t <= 6;++t)
						if ((t == i || t == j || t == k) && q[t] == mx)
							cur.pb(t);
					int med = q[i] + q[j] + q[k] - mn - mx;
					for (int t = 1;t <= 6;++t)
						if ((t == i || t == j || t == k) && q[t] == med)
							cur.pb(t);
				}
		for (int i = 1;i <= 6;++i)
			for (int j = i + 1;j <= 6;++j)
				for (int k = j + 1;k <= 6;++k) {
					for (int t = 1;t <= 6;++t)
						if (t != i && t != j && t != k) {
							set < int > ss;
							if (q[i] > q[t])
								ss.insert(i);
							if (q[j] > q[t])
								ss.insert(j);
							if (q[k] > q[t])
								ss.insert(k);
							if (ss.empty()) {
								ss.insert(i);
								ss.insert(j);
								ss.insert(k);
							}
							int mn = 1e9;
							for (auto it : ss)
								smin(mn,q[it]);
							for (auto it : ss)
								if (q[it] == mn)
									cur.pb(it);
						}
				}
		M[p] = cur;
	} while (next_permutation(all(p)));
	int step = 0;
	while (M.size() > 1) {
		++step;
		vector < vi > ss;
		vector < vi > SS;
		for (auto it : M)
			ss.pb(it.se),SS.pb(it.fi);
		int n1 = ss.size();
		int m1 = ss[0].size();
		vector < pii > vv;
		for (int j = 0;j < m1;++j)
			if (!was[j]) {
				map < int , int > mm;
				for (int i = 0;i < n1;++i)
					++mm[ss[i][j]];
				multiset < int > S;
				for (auto it : mm)
					S.insert(it.se);
				if (S.size() > 1)
					vv.pb(mp(*S.rbegin(),j));
			}
		int mn = min_element(all(vv))->fi;
		vi index;
		/*
		for (auto it : vv)
			if (it.fi == BL[step])
				index.pb(it.se);
		*/
		if (index.empty()) {
			for (auto it : vv)
				if (it.fi == mn)
					index.pb(it.se);
		}
		if (*max_element(all(index)) >= 60) {
			auto nw = index;
			nw.clear();
			for (auto it : nw)
				if (it >= 60)
					index.pb(it);
		}
		int ind = index.back();
		was[ind] = 1;
		int Query = -1;
		int chosed = -1;
		for (int i = 1;i <= 6;++i)
			for (int j = i + 1;j <= 6;++j)
				for (int k = j + 1;k <= 6;++k) {
					++Query;
					if (Query == ind) {
						chosed = getLightest(i,j,k);
					}
					++Query;
					if (Query == ind) {
						chosed = getHeaviest(i,j,k);
					}
					++Query;
					if (Query == ind) {
						chosed = getMedian(i,j,k);
					}
				}
		for (int i = 1;i <= 6;++i)
			for (int j = i + 1;j <= 6;++j)
				for (int k = j + 1;k <= 6;++k)
					for (int t = 1;t <= 6;++t) 
						if (t != i && t != j && t != k) {
							++Query;
							if (Query == ind) {
								chosed = getNextLightest(i,j,k,t);
							}
						}
		for (auto it : SS)
			if (M[it][ind] != chosed) {
				M.erase(it);
			}
	}
	auto ans = M.begin()->fi;
   	answer(ans.data());
}

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:22:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^
scales.cpp: In function 'void orderCoins()':
scales.cpp:95:19: warning: conversion to 'int' from 'std::vector<std::vector<int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   int n1 = ss.size();
            ~~~~~~~^~
scales.cpp:96:22: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   int m1 = ss[0].size();
            ~~~~~~~~~~^~

• Subtask 1: 72.916667 / 100