Submission #621332

#	Time	Username	Problem	Language	Result	Execution time	Memory
621332		M_W	Scales (IOI15_scales)	C++17	71.43 / 100	43 ms	432 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()));
}

void orderCoins(){
	vector<vector<int>> cases = all_perm;
	while(cases.size() > 1){
		array<int, 7> ask = {INT_MAX, 0, 0, 0, 0, 0, 0};
		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(max({hi, hj, hk}) < ask[0] || (max({hi, hj, hk}) == ask[0] && min({hi, hj, hk}) < ask[6]))  
						ask = {max({hi, hj, hk}), 1, i, j, k, 0, min({hi, hj, hk})};
					
					if(max({li, lj, lk}) < ask[0] || (max({li, lj, lk}) == ask[0] && min({li, lj, lk}) < ask[6])) 
						ask = {max({li, lj, lk}), 2, i, j, k, 0, min({li, lj, lk})};
					
					if(max({mi, mj, mk}) < ask[0] || (max({mi, mj, mk}) == ask[0] && min({mi, mj, mk}) < ask[6])) 
						ask = {max({mi, mj, mk}), 3, i, j, k, 0, min({mi, mj, mk})};
					
					// Case4: GetNextLightest
					for(int l = 1; l < k; l++){
						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(max({si, sj, sk}) < ask[0] || (max({si, sj, sk}) == ask[0] && min({si, sj, sk}) < ask[6])) 
							ask = {max({si, sj, sk}), 4, i, j, k, l, min({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 'void orderCoins()':
scales.cpp:135:17: warning: declaration of 'tmp' shadows a previous local [-Wshadow]
  135 |     vector<int> tmp = {ii, jj, kk};
      |                 ^~~
scales.cpp:83:23: note: shadowed declaration is here
   83 |   vector<vector<int>> tmp = cases; cases.clear();
      |                       ^~~
scales.cpp:140:5: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  140 |     if(upb == rr) cases.push_back(x);
      |     ^~
scales.cpp:127:17: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |     int ii, jj, kk, rr;
      |                 ^~
scales.cpp:127:13: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |     int ii, jj, kk, rr;
      |             ^~
scales.cpp:127:9: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |     int ii, jj, kk, rr;
      |         ^~
scales.cpp:137:6: warning: 'l2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  137 |      if(y > l2) upb = min(upb, y);
      |      ^~
scales.cpp:120:32: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |     if(min({ii, jj, kk}) != rr && max({ii, jj, kk}) != rr) cases.push_back(x);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:113:17: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |     int ii, jj, kk, rr;
      |                 ^~
scales.cpp:113:13: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |     int ii, jj, kk, rr;
      |             ^~
scales.cpp:113:9: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |     int ii, jj, kk, rr;
      |         ^~
scales.cpp:107:5: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  107 |     if(min({ii, jj, kk}) == rr) cases.push_back(x);
      |     ^~
scales.cpp:100:17: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |     int ii, jj, kk, rr;
      |                 ^~
scales.cpp:100:13: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |     int ii, jj, kk, rr;
      |             ^~
scales.cpp:100:9: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |     int ii, jj, kk, rr;
      |         ^~
scales.cpp:94:5: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |     if(max({ii, jj, kk}) == rr) cases.push_back(x);
      |     ^~
scales.cpp:87:17: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |     int ii, jj, kk, rr;
      |                 ^~
scales.cpp:87:13: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |     int ii, jj, kk, rr;
      |             ^~
scales.cpp:87:9: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |     int ii, jj, kk, rr;
      |         ^~
scales.cpp:43:34: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |       if(min({ii, jj, kk}) != kk && max({ii, jj, kk}) != kk) mk++;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:42:34: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |       if(min({ii, jj, kk}) != jj && max({ii, jj, kk}) != jj) mj++;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:41:34: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |       if(min({ii, jj, kk}) != ii && max({ii, jj, kk}) != ii) mi++;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 71.428571 / 100