Submission #1244270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244270		moondarkside	Scales (IOI15_scales)	C++20	71.43 / 100	152 ms	616 KiB

scales

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

void init(int T) {
	return;
}


int BestComb(vector<vector<int>> Combs) {


	if(Combs.size()==1) {


		int W[6];
		for(int i=0; i<6; i++) {
			W[Combs[0][i]]=i+1;
		}
		answer(W);
		return 0;
	}
	
	vector<int> BestW;
	int bestSplit=Combs.size()+1;
	vector<vector<int>> A;
	vector<vector<int>> B;
	vector<vector<int>> C;
	for(int a=0; a<6; a++) {
		for(int b=a+1; b<6; b++) {
			for(int c=b+1; c<6; c++) {
				vector<vector<int>> Am;
				vector<vector<int>> Bm;
				vector<vector<int>> Cm;
				for(int i=0; i<Combs.size(); i++) {



					if(Combs[i][a]>Combs[i][b] && Combs[i][a]>Combs[i][c]) {
						Am.push_back(Combs[i]);
					}

					if(Combs[i][b]>Combs[i][c] && Combs[i][b]>Combs[i][a]) {
						Bm.push_back(Combs[i]);
					}

					if(Combs[i][c]>Combs[i][b] && Combs[i][c]>Combs[i][a]) {
						Cm.push_back(Combs[i]);
					}



				}
				int size=max(Am.size(),max(Bm.size(),Cm.size()));
				if(size<bestSplit) {
					bestSplit=size;
					A=Am;
					B=Bm;
					C=Cm;
					BestW= {2,a,b,c};
				}
			}
		}
	}


	for(int a=0; a<6; a++) {
		for(int b=a+1; b<6; b++) {
			for(int c=b+1; c<6; c++) {
				vector<vector<int>> Am;
				vector<vector<int>> Bm;
				vector<vector<int>> Cm;
				for(int i=0; i<Combs.size(); i++) {



					if(Combs[i][a]<Combs[i][b] && Combs[i][a]<Combs[i][c]) {
						Am.push_back(Combs[i]);
					}

					if(Combs[i][b]<Combs[i][c] && Combs[i][b]<Combs[i][a]) {
						Bm.push_back(Combs[i]);
					}

					if(Combs[i][c]<Combs[i][b] && Combs[i][c]<Combs[i][a]) {
						Cm.push_back(Combs[i]);
					}



				}
				int size=max(Am.size(),max(Bm.size(),Cm.size()));
				if(size<bestSplit) {
					bestSplit=size;
					A=Am;
					B=Bm;
					C=Cm;
					BestW= {0,a,b,c};
				}
			}
		}
	}

	for(int a=0; a<6; a++) {
		for(int b=a+1; b<6; b++) {
			for(int c=b+1; c<6; c++) {
				vector<vector<int>> Am;
				vector<vector<int>> Bm;
				vector<vector<int>> Cm;
				for(int i=0; i<Combs.size(); i++) {



					if(Combs[i][a]<Combs[i][b] && Combs[i][a]>Combs[i][c]) {
						Am.push_back(Combs[i]);
					}

					if(Combs[i][a]>Combs[i][b] && Combs[i][a]<Combs[i][c]) {
						Am.push_back(Combs[i]);
					}

					if(Combs[i][b]<Combs[i][c] && Combs[i][b]>Combs[i][a]) {
						Bm.push_back(Combs[i]);
					}

					if(Combs[i][b]>Combs[i][c] && Combs[i][b]<Combs[i][a]) {
						Bm.push_back(Combs[i]);
					}

					if(Combs[i][c]<Combs[i][b] && Combs[i][c]>Combs[i][a]) {
						Cm.push_back(Combs[i]);
					}

					if(Combs[i][c]>Combs[i][b] && Combs[i][c]<Combs[i][a]) {
						Cm.push_back(Combs[i]);
					}



				}
				int size=max(Am.size(),max(Bm.size(),Cm.size()));
				if(size<bestSplit) {
					bestSplit=size;
					A=Am;
					B=Bm;
					C=Cm;
					BestW= {1,a,b,c};
				}
			}
		}
	}

	for(int d=0; d<6; d++) {
		for(int a=0; a<6; a++) {
			for(int b=a+1; b<6; b++) {
				for(int c=b+1; c<6; c++) {
					if(a!=d && b!=d && c!=d) {
						vector<vector<int>> Am;
						vector<vector<int>> Bm;
						vector<vector<int>> Cm;
						for(int i=0; i<Combs.size(); i++) {



							vector<int> Temp= {Combs[i][a],Combs[i][b],Combs[i][c],Combs[i][d]};

							sort(Temp.begin(),Temp.end());

							int index=0;
							for(int j=0; j<4; j++) {
								if (Temp[j]==Combs[i][d]) {
									index=j;
								}
							}


							if(index<3) {
								index++;
							}
							else {
								index=0;
							}

							if(Temp[index]==Combs[i][a]) {
								Am.push_back(Combs[i]);
							}

							if(Temp[index]==Combs[i][b]) {
								Bm.push_back(Combs[i]);
							}

							if(Temp[index]==Combs[i][c]) {
								Cm.push_back(Combs[i]);
							}



						}
						int size=max(Am.size(),max(Bm.size(),Cm.size()));
						if(size<bestSplit) {
							bestSplit=size;
							A=Am;
							B=Bm;
							C=Cm;
							BestW= {3,a,b,c,d};
						}
					}
				}
			}
		}
	}

	int best=0;
	if(BestW[0]==0) {
		best=getLightest(BestW[1]+1,BestW[2]+1,BestW[3]+1);
	}
	if(BestW[0]==1) {
		best=getMedian(BestW[1]+1,BestW[2]+1,BestW[3]+1);
	}
	if(BestW[0]==2) {
		best=getHeaviest(BestW[1]+1,BestW[2]+1,BestW[3]+1);
	}
	if(BestW[0]==3) {
		best=getNextLightest(BestW[1]+1,BestW[2]+1,BestW[3]+1,BestW[4]+1);
	}

	best--;
	if(best==BestW[1]) {
		return BestComb(A)+1;
	}

	if(best==BestW[2]) {
		return BestComb(B)+1;
	}

	if(best==BestW[3]) {
		return BestComb(C)+1;
	}

	return 1;
}


void buildPerm(vector<bool> Chosen,vector<vector<int>>& Perms,vector<int> T) {
	if(T.size()==6) {
		Perms.push_back(T);
		return;
	}

	for(int i=0; i<6; i++) {
		if(!Chosen[i]) {
			Chosen[i]=true;
			T.push_back(i);
			buildPerm(Chosen,Perms,T);
			T.pop_back();
			Chosen[i]=false;

		}
	}



}

void orderCoins() {
	vector<vector<int>> Perms;
	vector<bool> C(6,false);
	buildPerm(C,Perms,vector<int>(0));
	BestComb(Perms);
	return;

}

• Subtask 1: 71.4286 / 100