Submission #621384

#	Time	Username	Problem	Language	Result	Execution time	Memory
621384		M_W	Scales (IOI15_scales)	C++17	73.81 / 100	102 ms	412 KiB

scales

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

void init(int T){
	vector<int> perm = {1, 2, 3, 4, 5, 6};
	do{
		all_perm.push_back(perm);
	} while(next_permutation(perm.begin(), perm.end()));
}

bool condition(int i1, int j1, int k1, int i2, int j2, int k2){
	// Check to choose 1 instead of 2
	int mx1 = max({i1, j1, k1}), mx2 = max({i2, j2, k2});
	int mn1 = min({i1, j1, k1}), mn2 = min({i2, j2, k2});
	int sm1 = i1 + j1 + k1, sm2 = i2 + j2 + k2;
	
	return mx1 <= mx2;
}

void orderCoins(){
	vector<vector<int>> cases = all_perm;
	while(cases.size() > 1){
		array<int, 9> ask = {INT_MAX, 0, 0, 0, 0, 0, 1000, 1000, 1000};
		for(int i = 1; i <= 6; i++){
			for(int j = 1; j < i; j++){
				for(int k = 1; k < j; k++){
					int hi = 0, hj = 0, hk = 0; // heavy count (case left)
					int li = 0, lj = 0, lk = 0; // light count (case left)
					int mi = 0, mj = 0, mk = 0; // median count (case left)
					for(auto x : cases){
						int ii, jj, kk;
						for(int p = 0; p < 6; p++){
							if(x[p] == i) ii = p;
							if(x[p] == j) jj = p;
							if(x[p] == k) kk = p;
						}
						// Case1: Getheaviest
						if(max({ii, jj, kk}) == ii) hi++;
						if(max({ii, jj, kk}) == jj) hj++;
						if(max({ii, jj, kk}) == kk) hk++;
						
						// Case2: Getlightest
						if(min({ii, jj, kk}) == ii) li++;
						if(min({ii, jj, kk}) == jj) lj++;
						if(min({ii, jj, kk}) == kk) lk++;
						
						// Case3: GetMedian
						if(min({ii, jj, kk}) != ii && max({ii, jj, kk}) != ii) mi++;
						if(min({ii, jj, kk}) != jj && max({ii, jj, kk}) != jj) mj++;
						if(min({ii, jj, kk}) != kk && max({ii, jj, kk}) != kk) mk++;
					}
					if(condition(hi, hj, hk, ask[6], ask[7], ask[8]))
						ask = {max({hi, hj, hk}), 1, i, j, k, 0, hi, hj, hk};
					
					if(condition(li, lj, lk, ask[6], ask[7], ask[8]))
						ask = {max({li, lj, lk}), 2, i, j, k, 0, li, lj, lk};
					
					if(condition(mi, mj, mk, ask[6], ask[7], ask[8]))
						ask = {max({mi, mj, mk}), 3, i, j, k, 0, mi, mj, mk};
					
					// Case4: GetNextLightest
					for(int l = 1; l < 6; l++){
						if(l == i || l == j || l == k) continue;
						int si = 0, sj = 0, sk = 0;
						for(auto x : cases){
							int l2, upb = 10;
							int ii, jj, kk;
							for(int p = 0; p < 6; p++){
								if(x[p] == i) ii = p;
								if(x[p] == j) jj = p;
								if(x[p] == k) kk = p;
								if(x[p] == l) l2 = p;
							}
							vector<int> tmp = {ii, jj, kk};
							for(auto y : tmp){
								if(y > l2) upb = min(upb, y);
							}
							if(upb == 10) upb = min({ii, jj, kk});
							
							if(ii == upb) si++;
							if(jj == upb) sj++;
							if(kk == upb) sk++;
						}
						if(condition(si, sj, sk, ask[6], ask[7], ask[8]))
							ask = {max({si, sj, sk}), 4, i, j, k, l, si, sj, sk};
					}
				}
			}
		}

		int res;
		vector<vector<int>> tmp = cases; cases.clear();
		if(ask[1] == 1){
			res = getHeaviest(ask[2], ask[3], ask[4]);
			for(auto x : tmp){
				int ii, jj, kk, rr;
				for(int p = 0; p < 6; p++){
					if(x[p] == ask[4]) ii = p;
					if(x[p] == ask[2]) jj = p;
					if(x[p] == ask[3]) kk = p;
					if(x[p] == res) rr = p;
				}
				if(max({ii, jj, kk}) == rr) cases.push_back(x);
			}
		}
		else if(ask[1] == 2){
			res = getLightest(ask[4], ask[2], ask[3]);
			for(auto x : tmp){
				int ii, jj, kk, rr;
				for(int p = 0; p < 6; p++){
					if(x[p] == ask[4]) ii = p;
					if(x[p] == ask[2]) jj = p;
					if(x[p] == ask[3]) kk = p;
					if(x[p] == res) rr = p;
				}
				if(min({ii, jj, kk}) == rr) cases.push_back(x);
			}
		}
		else if(ask[1] == 3){
			res = getMedian(ask[4], ask[2], ask[3]);
			for(auto x : tmp){
				int ii, jj, kk, rr;
				for(int p = 0; p < 6; p++){
					if(x[p] == ask[4]) ii = p;
					if(x[p] == ask[2]) jj = p;
					if(x[p] == ask[3]) kk = p;
					if(x[p] == res) rr = p;
				}
				if(min({ii, jj, kk}) != rr && max({ii, jj, kk}) != rr) cases.push_back(x);
			}
		}
		else{
			res = getNextLightest(ask[2], ask[3], ask[4], ask[5]);
			for(auto x : tmp){
				int l2, upb = 10;
				int ii, jj, kk, rr;
				for(int p = 0; p < 6; p++){
					if(x[p] == ask[2]) ii = p;
					if(x[p] == ask[3]) jj = p;
					if(x[p] == ask[4]) kk = p;
					if(x[p] == ask[5]) l2 = p;
					if(x[p] == res) rr = p;
				}
				vector<int> tmp = {ii, jj, kk};
				for(auto y : tmp){
					if(y > l2) upb = min(upb, y);
				}
				if(upb == 10) upb = min({ii, jj, kk});
				if(upb == rr) cases.push_back(x);
			}
		}
	}
	int ans[] = {cases[0][0], cases[0][1], cases[0][2], cases[0][3], cases[0][4], cases[0][5]};
	answer(ans);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:6:15: warning: unused parameter 'T' [-Wunused-parameter]
    6 | void init(int T){
      |           ~~~~^
scales.cpp: In function 'bool condition(int, int, int, int, int, int)':
scales.cpp:16:6: warning: unused variable 'mn1' [-Wunused-variable]
   16 |  int mn1 = min({i1, j1, k1}), mn2 = min({i2, j2, k2});
      |      ^~~
scales.cpp:16:31: warning: unused variable 'mn2' [-Wunused-variable]
   16 |  int mn1 = min({i1, j1, k1}), mn2 = min({i2, j2, k2});
      |                               ^~~
scales.cpp:17:6: warning: unused variable 'sm1' [-Wunused-variable]
   17 |  int sm1 = i1 + j1 + k1, sm2 = i2 + j2 + k2;
      |      ^~~
scales.cpp:17:26: warning: unused variable 'sm2' [-Wunused-variable]
   17 |  int sm1 = i1 + j1 + k1, sm2 = i2 + j2 + k2;
      |                          ^~~
scales.cpp: In function 'void orderCoins()':
scales.cpp:146:17: warning: declaration of 'tmp' shadows a previous local [-Wshadow]
  146 |     vector<int> tmp = {ii, jj, kk};
      |                 ^~~
scales.cpp:94:23: note: shadowed declaration is here
   94 |   vector<vector<int>> tmp = cases; cases.clear();
      |                       ^~~
scales.cpp:151:5: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  151 |     if(upb == rr) cases.push_back(x);
      |     ^~
scales.cpp:138:17: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
  138 |     int ii, jj, kk, rr;
      |                 ^~
scales.cpp:138:13: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  138 |     int ii, jj, kk, rr;
      |             ^~
scales.cpp:138:9: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
  138 |     int ii, jj, kk, rr;
      |         ^~
scales.cpp:148:6: warning: 'l2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  148 |      if(y > l2) upb = min(upb, y);
      |      ^~
scales.cpp:131:32: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  131 |     if(min({ii, jj, kk}) != rr && max({ii, jj, kk}) != rr) cases.push_back(x);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:124:17: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |     int ii, jj, kk, rr;
      |                 ^~
scales.cpp:124:13: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |     int ii, jj, kk, rr;
      |             ^~
scales.cpp:124:9: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |     int ii, jj, kk, rr;
      |         ^~
scales.cpp:118:5: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |     if(min({ii, jj, kk}) == rr) cases.push_back(x);
      |     ^~
scales.cpp:111:17: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |     int ii, jj, kk, rr;
      |                 ^~
scales.cpp:111:13: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |     int ii, jj, kk, rr;
      |             ^~
scales.cpp:111:9: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |     int ii, jj, kk, rr;
      |         ^~
scales.cpp:105:5: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |     if(max({ii, jj, kk}) == rr) cases.push_back(x);
      |     ^~
scales.cpp:98:17: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     int ii, jj, kk, rr;
      |                 ^~
scales.cpp:98:13: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     int ii, jj, kk, rr;
      |             ^~
scales.cpp:98:9: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     int ii, jj, kk, rr;
      |         ^~
scales.cpp:69:20: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |        int ii, jj, kk;
      |                    ^~
scales.cpp:69:16: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |        int ii, jj, kk;
      |                ^~
scales.cpp:69:12: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |        int ii, jj, kk;
      |            ^~
scales.cpp:78:9: warning: 'l2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |         if(y > l2) upb = min(upb, y);
      |         ^~
scales.cpp:52:34: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |       if(min({ii, jj, kk}) != kk && max({ii, jj, kk}) != kk) mk++;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:51:34: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |       if(min({ii, jj, kk}) != jj && max({ii, jj, kk}) != jj) mj++;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:50:34: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |       if(min({ii, jj, kk}) != ii && max({ii, jj, kk}) != ii) mi++;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 73.809524 / 100