Submission #1244095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244095		moondarkside	Scales (IOI15_scales)	C++20	0 / 100	6 ms	576 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[i]=Combs[0][i];
        }
        answer(W);
        return 0;
    }
	vector<int> BestW;
	int bestSplit=Combs.size();
	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][c]) {
						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][b]<Combs[i][c] && Combs[i][b]<Combs[i][c]) {
						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= {1,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][c]) {
						Bm.push_back(Combs[i]);
					}

					if(Combs[i][b]>Combs[i][c] && Combs[i][b]<Combs[i][c]) {
						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= {2,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],BestW[2],BestW[3]);
    }
    if(BestW[0]==1){
        best=getMedian(BestW[1],BestW[2],BestW[3]);
    }
    if(BestW[0]==2){
        best=getHeaviest(BestW[1],BestW[2],BestW[3]);
    }
    if(BestW[0]==3){
        best=getNextLightest(BestW[1],BestW[2],BestW[3],BestW[4]);
    }

    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);
	buildPerm(C,Perms,vector<int>());
	BestComb(Perms);

}

• Subtask 1: 0 / 100