oj.uz

Submission #115515

# Submission time Handle Problem Language Result Execution time Memory
115515 2019-06-08T02:53:30 Z E869120 Scales (IOI15_scales) C++14
100 / 100
 529 ms 640 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 512 KB Output is correct
2 Correct 343 ms 632 KB Output is correct
3 Correct 529 ms 512 KB Output is correct
4 Correct 344 ms 512 KB Output is correct
5 Correct 359 ms 632 KB Output is correct
6 Correct 345 ms 512 KB Output is correct
7 Correct 340 ms 528 KB Output is correct
8 Correct 339 ms 512 KB Output is correct
9 Correct 341 ms 512 KB Output is correct
10 Correct 350 ms 512 KB Output is correct
11 Correct 335 ms 512 KB Output is correct
12 Correct 353 ms 632 KB Output is correct
13 Correct 345 ms 512 KB Output is correct
14 Correct 346 ms 632 KB Output is correct
15 Correct 346 ms 640 KB Output is correct
16 Correct 356 ms 512 KB Output is correct
17 Correct 357 ms 632 KB Output is correct
18 Correct 373 ms 632 KB Output is correct
19 Correct 342 ms 512 KB Output is correct
20 Correct 347 ms 512 KB Output is correct
21 Correct 337 ms 632 KB Output is correct
22 Correct 347 ms 604 KB Output is correct
23 Correct 361 ms 512 KB Output is correct
24 Correct 341 ms 512 KB Output is correct
25 Correct 345 ms 512 KB Output is correct
26 Correct 374 ms 632 KB Output is correct
27 Correct 350 ms 632 KB Output is correct
28 Correct 356 ms 632 KB Output is correct
29 Correct 341 ms 632 KB Output is correct
30 Correct 331 ms 640 KB Output is correct
31 Correct 333 ms 512 KB Output is correct
32 Correct 339 ms 528 KB Output is correct
33 Correct 336 ms 512 KB Output is correct
34 Correct 349 ms 636 KB Output is correct
35 Correct 336 ms 512 KB Output is correct
36 Correct 363 ms 632 KB Output is correct
37 Correct 351 ms 632 KB Output is correct
38 Correct 336 ms 632 KB Output is correct
39 Correct 349 ms 632 KB Output is correct
40 Correct 364 ms 632 KB Output is correct