Submission #115515

#	Time	Username	Problem	Language	Result	Execution time	Memory
115515		E869120	Scales (IOI15_scales)	C++14	100 / 100	529 ms	640 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;

void init(int T) {
    /* ... */
}

vector<int>vec;

int Query_1(int u1, int u2, int u3) {
	int id1, id2, id3;
	for (int i = 0; i < 6; i++) { if (u1 == vec[i]) id1 = i; }
	for (int i = 0; i < 6; i++) { if (u2 == vec[i]) id2 = i; }
	for (int i = 0; i < 6; i++) { if (u3 == vec[i]) id3 = i; }
	
	pair<int, int> G[3] = {make_pair(id1, u1), make_pair(id2, u2), make_pair(id3, u3)};
	sort(G, G + 3);
	return G[0].second;
}

int Query_2(int u1, int u2, int u3) {
	int id1, id2, id3;
	for (int i = 0; i < 6; i++) { if (u1 == vec[i]) id1 = i; }
	for (int i = 0; i < 6; i++) { if (u2 == vec[i]) id2 = i; }
	for (int i = 0; i < 6; i++) { if (u3 == vec[i]) id3 = i; }
	
	pair<int, int> G[3] = {make_pair(id1, u1), make_pair(id2, u2), make_pair(id3, u3)};
	sort(G, G + 3);
	return G[1].second;
}

int Query_3(int u1, int u2, int u3) {
	int id1, id2, id3;
	for (int i = 0; i < 6; i++) { if (u1 == vec[i]) id1 = i; }
	for (int i = 0; i < 6; i++) { if (u2 == vec[i]) id2 = i; }
	for (int i = 0; i < 6; i++) { if (u3 == vec[i]) id3 = i; }
	
	pair<int, int> G[3] = {make_pair(id1, u1), make_pair(id2, u2), make_pair(id3, u3)};
	sort(G, G + 3);
	return G[2].second;
}

int Query_4(int u1, int u2, int u3, int u4) {
	int id1, id2, id3, id4;
	for (int i = 0; i < 6; i++) { if (u1 == vec[i]) id1 = i; }
	for (int i = 0; i < 6; i++) { if (u2 == vec[i]) id2 = i; }
	for (int i = 0; i < 6; i++) { if (u3 == vec[i]) id3 = i; }
	for (int i = 0; i < 6; i++) { if (u4 == vec[i]) id4 = i; }
	
	pair<int, int> G[4] = {make_pair(id1, u1), make_pair(id2, u2), make_pair(id3, u3), make_pair(id4, u4)};
	sort(G, G + 4);
	
	for (int i = 0; i < 3; i++) {
		if (G[i].second == u4) return G[i + 1].second;
	}
	return G[0].second;
}

int CountMinimumPossibleMove(vector<vector<int>>vec1) {
	vector<vector<int>> minid[7]; int minx = (1 << 30);
	tuple<int, int, int, int, int> E;
	
	// Query 2: getMedian
	for (int i = 1; i <= 6; i++) {
		for (int j = i + 1; j <= 6; j++) {
			for (int k = j + 1; k <= 6; k++) {
				vector<vector<int>> sum[7];
				for (int l = 0; l < vec1.size(); l++) { vec = vec1[l]; sum[Query_2(i, j, k)].push_back(vec1[l]); }
				
				int minv = 0; for (int l = 1; l <= 6; l++) minv = max(minv, (int)sum[l].size()); //cout << minv << " ";
				if (minv < minx) { minx = minv; E = make_tuple(2, i, j, k, -1); for (int l = 1; l <= 6; l++) minid[l] = sum[l]; }
			}
		}
	}
	
	// Query 1: getLightest
	for (int i = 1; i <= 6; i++) {
		for (int j = i + 1; j <= 6; j++) {
			for (int k = j + 1; k <= 6; k++) {
				vector<vector<int>> sum[7];
				for (int l = 0; l < vec1.size(); l++) { vec = vec1[l]; sum[Query_1(i, j, k)].push_back(vec1[l]); }
				
				int minv = 0; for (int l = 1; l <= 6; l++) minv = max(minv, (int)sum[l].size()); //cout << minv << " ";
				if (minv < minx) { minx = minv; E = make_tuple(1, i, j, k, -1); for (int l = 1; l <= 6; l++) minid[l] = sum[l]; }
			}
		}
	}
	
	// Query 3: getHeaviest
	for (int i = 1; i <= 6; i++) {
		for (int j = i + 1; j <= 6; j++) {
			for (int k = j + 1; k <= 6; k++) {
				vector<vector<int>> sum[7];
				for (int l = 0; l < vec1.size(); l++) { vec = vec1[l]; sum[Query_3(i, j, k)].push_back(vec1[l]); }
				
				int minv = 0; for (int l = 1; l <= 6; l++) minv = max(minv, (int)sum[l].size()); //cout << minv << " ";
				if (minv < minx) { minx = minv; E = make_tuple(3, i, j, k, -1); for (int l = 1; l <= 6; l++) minid[l] = sum[l]; }
			}
		}
	}
	
	// Query 4: getNextLightest
	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 (i == t || j == t || k == t) continue;
					vector<vector<int>> sum[7];
					for (int l = 0; l < vec1.size(); l++) { vec = vec1[l]; sum[Query_4(i, j, k, t)].push_back(vec1[l]); }
					
					int minv = 0; for (int l = 1; l <= 6; l++) minv = max(minv, (int)sum[l].size()); //cout << minv << " ";
					if (minv < minx) { minx = minv; E = make_tuple(4, i, j, k, t); for (int l = 1; l <= 6; l++) minid[l] = sum[l]; }
				}
			}
		}
	}
	return minx;
}

vector<vector<int>> nextPossibleMove(vector<vector<int>> vec1) {
	vector<vector<int>> minid[7]; int minx = (1 << 30);
	tuple<int, int, int, int, int> E; bool complete = false;
	
	int B = 27;
	if (vec1.size() >= 200) B = 27;
	else if (vec1.size() >= 50) B = 9;
	
	// Query 2: getMedian
	for (int i = 1; i <= 6; i++) {
		for (int j = i + 1; j <= 6; j++) {
			for (int k = j + 1; k <= 6; k++) {
				if (complete == true) continue;
				vector<vector<int>> sum[7];
				for (int l = 0; l < vec1.size(); l++) { vec = vec1[l]; sum[Query_2(i, j, k)].push_back(vec1[l]); }
				
				int minv = 0; for (int l = 1; l <= 6; l++) minv = max(minv, (int)sum[l].size()); //cout << minv << " ";
				
				bool flag = true;
				if (vec1.size() >= 50 && vec1.size() <= 250 && minv <= B * 3) {
					for (int l = 1; l <= 6; l++) { if (CountMinimumPossibleMove(sum[l]) > B) flag = false; }
				}
				else flag = false;
				
				if (flag == true) complete = true;
				if (minv < minx || (minv == minx && flag == true)) { minx = minv; E = make_tuple(2, i, j, k, -1); for (int l = 1; l <= 6; l++) minid[l] = sum[l]; }
			}
		}
	}
	
	// Query 1: getLightest
	for (int i = 1; i <= 6; i++) {
		for (int j = i + 1; j <= 6; j++) {
			for (int k = j + 1; k <= 6; k++) {
				if (complete == true) continue;
				
				vector<vector<int>> sum[7];
				for (int l = 0; l < vec1.size(); l++) { vec = vec1[l]; sum[Query_1(i, j, k)].push_back(vec1[l]); }
				
				int minv = 0; for (int l = 1; l <= 6; l++) minv = max(minv, (int)sum[l].size()); //cout << minv << " ";
				
				bool flag = true;
				if (vec1.size() >= 50 && vec1.size() <= 250 && minv <= B * 3) {
					for (int l = 1; l <= 6; l++) { if (CountMinimumPossibleMove(sum[l]) > B) flag = false; }
				}
				else flag = false;
				
				if (flag == true) complete = true;
				if (minv < minx || (minv == minx && flag == true)) { minx = minv; E = make_tuple(1, i, j, k, -1); for (int l = 1; l <= 6; l++) minid[l] = sum[l]; }
			}
		}
	}
	
	// Query 3: getHeaviest
	for (int i = 1; i <= 6; i++) {
		for (int j = i + 1; j <= 6; j++) {
			for (int k = j + 1; k <= 6; k++) {
				if (complete == true) continue;
				
				vector<vector<int>> sum[7];
				for (int l = 0; l < vec1.size(); l++) { vec = vec1[l]; sum[Query_3(i, j, k)].push_back(vec1[l]); }
				
				int minv = 0; for (int l = 1; l <= 6; l++) minv = max(minv, (int)sum[l].size()); //cout << minv << " ";
				
				bool flag = true;
				if (vec1.size() >= 50 && vec1.size() <= 250 && minv <= B * 3) {
					for (int l = 1; l <= 6; l++) { if (CountMinimumPossibleMove(sum[l]) > B) flag = false; }
				}
				else flag = false;
				
				if (flag == true) complete = true;
				if (minv < minx || (minv == minx && flag == true)) { minx = minv; E = make_tuple(3, i, j, k, -1); for (int l = 1; l <= 6; l++) minid[l] = sum[l]; }
			}
		}
	}
	
	// Query 4: getNextLightest
	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 (complete == true) continue;
					if (i == t || j == t || k == t) continue;
					vector<vector<int>> sum[7];
					for (int l = 0; l < vec1.size(); l++) { vec = vec1[l]; sum[Query_4(i, j, k, t)].push_back(vec1[l]); }
					
					int minv = 0; for (int l = 1; l <= 6; l++) minv = max(minv, (int)sum[l].size()); //cout << minv << " ";
					
					bool flag = true;
					if (vec1.size() >= 50 && vec1.size() <= 250 && minv <= B * 3) {
						for (int l = 1; l <= 6; l++) { if (CountMinimumPossibleMove(sum[l]) > B) flag = false; }
					}
					else flag = false;
					
					if (flag == true) complete = true;
					if (minv < minx || (minv == minx && flag == true)) { minx = minv; E = make_tuple(4, i, j, k, t); for (int l = 1; l <= 6; l++) minid[l] = sum[l]; }
				}
			}
		}
	}
	
	// Summarize
	int G = 0;
	if (get<0>(E) == 1) G = getLightest(get<1>(E), get<2>(E), get<3>(E));
	if (get<0>(E) == 2) G = getMedian(get<1>(E), get<2>(E), get<3>(E));
	if (get<0>(E) == 3) G = getHeaviest(get<1>(E), get<2>(E), get<3>(E));
	if (get<0>(E) == 4) G = getNextLightest(get<1>(E), get<2>(E), get<3>(E), get<4>(E));
	return minid[G];
}

vector<int> solve() {
	vector<vector<int>> J; vector<int> K = {1, 2, 3, 4, 5, 6};
	
	do{
		J.push_back(K);
	}while(next_permutation(K.begin(), K.end()));
	
	while (J.size() >= 2) {
		//cout << J.size() << endl;
		J = nextPossibleMove(J);
	}
	return J[0];
}

void orderCoins() {
	vector<int> A = solve();
	int FinalAns[6]; for (int i = 0; i < A.size(); i++) FinalAns[i] = A[i];
	answer(FinalAns);
}

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:5:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^
scales.cpp: In function 'int CountMinimumPossibleMove(std::vector<std::vector<int> >)':
scales.cpp:69:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l = 0; l < vec1.size(); l++) { vec = vec1[l]; sum[Query_2(i, j, k)].push_back(vec1[l]); }
                     ~~^~~~~~~~~~~~~
scales.cpp:82:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l = 0; l < vec1.size(); l++) { vec = vec1[l]; sum[Query_1(i, j, k)].push_back(vec1[l]); }
                     ~~^~~~~~~~~~~~~
scales.cpp:95:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l = 0; l < vec1.size(); l++) { vec = vec1[l]; sum[Query_3(i, j, k)].push_back(vec1[l]); }
                     ~~^~~~~~~~~~~~~
scales.cpp:110:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int l = 0; l < vec1.size(); l++) { vec = vec1[l]; sum[Query_4(i, j, k, t)].push_back(vec1[l]); }
                      ~~^~~~~~~~~~~~~
scales.cpp: In function 'std::vector<std::vector<int> > nextPossibleMove(std::vector<std::vector<int> >)':
scales.cpp:135:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l = 0; l < vec1.size(); l++) { vec = vec1[l]; sum[Query_2(i, j, k)].push_back(vec1[l]); }
                     ~~^~~~~~~~~~~~~
scales.cpp:158:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l = 0; l < vec1.size(); l++) { vec = vec1[l]; sum[Query_1(i, j, k)].push_back(vec1[l]); }
                     ~~^~~~~~~~~~~~~
scales.cpp:181:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l = 0; l < vec1.size(); l++) { vec = vec1[l]; sum[Query_3(i, j, k)].push_back(vec1[l]); }
                     ~~^~~~~~~~~~~~~
scales.cpp:205:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int l = 0; l < vec1.size(); l++) { vec = vec1[l]; sum[Query_4(i, j, k, t)].push_back(vec1[l]); }
                      ~~^~~~~~~~~~~~~
scales.cpp: In function 'void orderCoins()':
scales.cpp:247:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  int FinalAns[6]; for (int i = 0; i < A.size(); i++) FinalAns[i] = A[i];
                                   ~~^~~~~~~~~~
scales.cpp: In function 'int Query_4(int, int, int, int)':
scales.cpp:51:103: warning: 'id4' may be used uninitialized in this function [-Wmaybe-uninitialized]
  pair<int, int> G[4] = {make_pair(id1, u1), make_pair(id2, u2), make_pair(id3, u3), make_pair(id4, u4)};
                                                                                                       ^
scales.cpp:51:103: warning: 'id3' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:51:103: warning: 'id2' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:51:103: warning: 'id1' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp: In function 'int Query_1(int, int, int)':
scales.cpp:17:83: warning: 'id3' may be used uninitialized in this function [-Wmaybe-uninitialized]
  pair<int, int> G[3] = {make_pair(id1, u1), make_pair(id2, u2), make_pair(id3, u3)};
                                                                                   ^
scales.cpp:17:83: warning: 'id2' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:17:83: warning: 'id1' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp: In function 'int Query_2(int, int, int)':
scales.cpp:28:83: warning: 'id3' may be used uninitialized in this function [-Wmaybe-uninitialized]
  pair<int, int> G[3] = {make_pair(id1, u1), make_pair(id2, u2), make_pair(id3, u3)};
                                                                                   ^
scales.cpp:28:83: warning: 'id2' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:28:83: warning: 'id1' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp: In function 'int Query_3(int, int, int)':
scales.cpp:39:83: warning: 'id3' may be used uninitialized in this function [-Wmaybe-uninitialized]
  pair<int, int> G[3] = {make_pair(id1, u1), make_pair(id2, u2), make_pair(id3, u3)};
                                                                                   ^
scales.cpp:39:83: warning: 'id2' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:39:83: warning: 'id1' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 100 / 100