Submission #66669

#	Time	Username	Problem	Language	Result	Execution time	Memory
66669		nvmdava	Scales (IOI15_scales)	C++17	0 / 100	1097 ms	20100 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
 
struct pos{
	int send[6], sort[7], mn[7][7][7], mx[7][7][7], md[7][7][7], qr[7][7][7][7];
 
	void fill(){
		for(int i = 0; i <= 5; i++){
			sort[send[i]] = i;	
		}
		vector<int> tmp(3, 0);
		int mnm,mxm,mdm, a;
		for(int i = 1; i < 5; i++){
			tmp[0] = i;
			for(int j = i + 1; j < 6; j++){
				tmp[1] = j;
				for(int l = j + 1; l <= 6; l++){
					tmp[2] = l;
					
					if(sort[i] < sort[j] && sort[j] < sort[l]){
						mnm = i;
						mdm = j;
						mxm = l;
					} else if(sort[i] < sort[l] && sort[l] < sort[j]){
						mnm = i;
						mdm = l;
						mxm = j;
					} else if(sort[j] < sort[i] && sort[i] < sort[l]){
						mnm = j;
						mdm = i;
						mxm = l;
					} else if(sort[j] < sort[l] && sort[l] < sort[i]){
						mnm = j;
						mdm = l;
						mxm = i;
					} else if(sort[l] < sort[i] && sort[i] < sort[j]){
						mnm = l;
						mdm = i;
						mxm = j;
					} else {
						mnm = l;
						mdm = j;
						mxm = i;
					}
					
					do{
						mn[tmp[0]][tmp[1]][tmp[2]] = mnm;
						mx[tmp[0]][tmp[1]][tmp[2]] = mxm;
						md[tmp[0]][tmp[1]][tmp[2]] = mdm;
					} while(next_permutation(tmp.begin(), tmp.end()));
					for(int t = 1; t <= 6; t++){
						if(i == t || t == j || t == l){
							continue;
						}
						if(sort[t] < sort[mnm]){
							a = mnm;
						} else if(sort[t] < sort[mdm]){
							a = mdm;
						} else if(sort[t] < sort[mxm]){
							a = mxm;
						} else {
							a = mnm;
						}
						
						do{
							qr[tmp[0]][tmp[1]][tmp[2]][t] = a;
						} while(next_permutation(tmp.begin(), tmp.end()));
						
					}
				}
			}
		}
		
	}
};
pos all[720];
vector<pos> v;
vector<int> tmp = {1, 2, 3, 4, 5, 6};
void init(int T) {
	int s = 0;
	do{
		for(int i = 0; i < 5; i++){
			all[s].send[i] = tmp[i];
		}
		all[s].fill();
		s++; 
	} while(next_permutation(tmp.begin(), tmp.end()));
}

void orderCoins() {
	v.insert(v.begin(), all + 0, all + 720);
	while(v.size() != 1){
 		int A, B, C, D, res[4], dif = 1001, type = 0;
		//Find best query;
		for(int i = 1; i < 5; i++){
			for(int j = i + 1; j < 6; j++){
				for(int l = j + 1; l <= 6; l++){
					memset(res, 0, sizeof(res));
					for(auto x : v){
						if(x.mn[i][j][l] == i){
							res[1]++;
						} else if(x.mn[i][j][l] == j){
							res[2]++;
						} else {
							res[0]++;
						}
					}
					if(dif > max(res[0], max(res[1], res[2])) - min(res[0], min(res[1], res[2]))){
						dif = max(res[0], max(res[1], res[2])) - min(res[0], min(res[1], res[2]));
						type = 1;
						A = i;
						B = j;
						C = l;
					}
				}
			}
		}
		for(int i = 1; i < 5; i++){
			for(int j = i + 1; j < 6; j++){
				for(int l = j + 1; l <= 6; l++){
					memset(res, 0, sizeof(res));
					for(auto x : v){
						if(x.md[i][j][l] == i){
							res[1]++;
						} else if(x.md[i][j][l] == j){
							res[2]++;
						} else {
							res[0]++;
						}
					}
					if(dif > max(res[0], max(res[1], res[2])) - min(res[0], min(res[1], res[2]))){
						dif = max(res[0], max(res[1], res[2])) - min(res[0], min(res[1], res[2]));
						type = 2;
						A = i;
						B = j;
						C = l;
					}
				}
			}
		}
		for(int i = 1; i < 5; i++){
			for(int j = i + 1; j < 6; j++){
				for(int l = j + 1; l <= 6; l++){
					memset(res, 0, sizeof(res));
					for(auto x : v){
						if(x.mx[i][j][l] == i){
							res[1]++;
						} else if(x.mx[i][j][l] == j){
							res[2]++;
						} else {
							res[0]++;
						}
					}
					if(dif > max(res[0], max(res[1], res[2])) - min(res[0], min(res[1], res[2]))){
						dif = max(res[0], max(res[1], res[2])) - min(res[0], min(res[1], res[2]));
						type = 3;
						A = i;
						B = j;
						C = l;
					}
				}
			}
		}
		for(int i = 1; i < 5; i++){
			for(int j = i + 1; j < 6; j++){
				for(int l = j + 1; l <= 6; l++){
					for(int t = 1; t <= 6; t++){
						if(t == i || t == j || t == l){
							continue;
						}
						memset(res, 0, sizeof(res));
						for(auto x : v){
							if(x.qr[i][j][l][t] == i){
								res[1]++;
							} else if(x.qr[i][j][l][t] == j){
								res[2]++;
							} else {
								res[0]++;
							}
						}
						if(dif > max(res[0], max(res[1], res[2])) - min(res[0], min(res[1], res[2]))){
							dif = max(res[0], max(res[1], res[2])) - min(res[0], min(res[1], res[2]));
							type = 4;
							A = i;
							B = j;
							C = l;
							D = t;
						}
					}
				}
			}
		}
		//Ask best query;
		if(type == 1){
			res[0] = getLightest(A, B, C);
			for(int i = 0; i < v.size(); i++){
				if(v[i].mn[A][B][C] != res[0]){
					v.erase(v.begin() + i);
					i--;
				}
			}
		} else if(type == 2){
			res[0] = getMedian(A, B, C);
			for(int i = 0; i < v.size(); i++){
				if(v[i].md[A][B][C] != res[0]){
					v.erase(v.begin() + i);
					i--;
				}
			}
		} else if(type == 3){
			res[0] = getHeaviest(A, B, C);
			for(int i = 0; i < v.size(); i++){
				if(v[i].mx[A][B][C] != res[0]){
					v.erase(v.begin() + i);
					i--;
				}
			}
		} else {
			res[0] = getNextLightest(A, B, C, D);
			
			for(int i = 0; i < v.size(); i++){
				if(v[i].qr[A][B][C][D] != res[0]){
					v.erase(v.begin() + i);
					i--;
				}
			}
		}		
	}

	answer(v[0].send);
}

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:80:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^
scales.cpp: In function 'void orderCoins()':
scales.cpp:197:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < v.size(); i++){
                   ~~^~~~~~~~~~
scales.cpp:205:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < v.size(); i++){
                   ~~^~~~~~~~~~
scales.cpp:213:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < v.size(); i++){
                   ~~^~~~~~~~~~
scales.cpp:222:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < v.size(); i++){
                   ~~^~~~~~~~~~
scales.cpp:223:26: warning: 'D' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(v[i].qr[A][B][C][D] != res[0]){
        ~~~~~~~~~~~~~~~~~~^
scales.cpp:223:26: warning: 'C' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:223:26: warning: 'B' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:223:26: warning: 'A' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 0 / 100