Submission #31175

#	Time	Username	Problem	Language	Result	Execution time	Memory
31175		cscandkswon	Scales (IOI15_scales)	C++14	100 / 100	13 ms	2068 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXQ=120;
const int MAXP=720;

struct Question{
	int type, a, b, c, d;
} Q[MAXQ];

struct Permutation{
	int A[7];
} P[MAXP];

int order[5000];

int getL(Permutation list, int a, int b, int c){
	if(list.A[a]<list.A[b] && list.A[a]<list.A[c]) return 0;
	else if(list.A[b]<list.A[c]) return 1;
	return 2;
}

int getH(Permutation list, int a, int b, int c){
	if(list.A[a]>list.A[b] && list.A[a]>list.A[c]) return 0;
	else if(list.A[b]>list.A[c]) return 1;
	return 2;
}

int getM(Permutation list, int a, int b, int c){
	if(min(list.A[b], list.A[c])<list.A[a]&&list.A[a]<max(list.A[b], list.A[c])) return 0;
	else if(min(list.A[a], list.A[c])<list.A[b]&&list.A[b]<max(list.A[a], list.A[c])) return 1;
	return 2;
}

int getN(Permutation list, int a, int b, int c, int d){
	int x=(list.A[d]<list.A[a]), y=(list.A[d]<list.A[b]), z=(list.A[d]<list.A[c]);
	if(x&&y&&z) return getL(list, a, b, c);
	else if(x&&y){
		if(list.A[a]<list.A[b]) return 0;
		else return 1;
	}
	else if(x&&z){
		if(list.A[a]<list.A[c]) return 0;
		else return 2;
	}
	else if(y&&z){
		if(list.A[b]<list.A[c]) return 1;
		return 2;
	}
	else if(x) return 0;
	else if(y) return 1;
	else if(z) return 2;
	else return getL(list, a, b, c);
}

int makeorder(int lev, vector<int> list, int idx){
	if(lev==6){
		if(list.size()==1)
			order[idx]=list[0];
		return 1;
	}
	int i, j, rv, cnt[3]={0};
	for(i=0; i<MAXQ; i++){
		cnt[0]=cnt[1]=cnt[2]=0;
		for(j=0; j<list.size(); j++){
			if(Q[i].type==1) rv=getL(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
			else if(Q[i].type==2) rv=getH(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
			else if(Q[i].type==3) rv=getM(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
			else rv=getN(P[list[j]], Q[i].a, Q[i].b, Q[i].c, Q[i].d);
			cnt[rv]++;
		}
		if(max(cnt[0], max(cnt[1], cnt[2]))-min(cnt[0], min(cnt[1], cnt[2]))<=1){
			vector<int> lst[3];
			for(j=0; j<list.size(); j++){
				if(Q[i].type==1) rv=getL(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
				else if(Q[i].type==2) rv=getH(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
				else if(Q[i].type==3) rv=getM(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
				else rv=getN(P[list[j]], Q[i].a, Q[i].b, Q[i].c, Q[i].d);
				lst[rv].push_back(list[j]);
			}
			rv=makeorder(lev+1, lst[0], idx*3-1);
			if(!rv) continue;
			rv=makeorder(lev+1, lst[1], idx*3);
			if(!rv) continue;
			rv=makeorder(lev+1, lst[2], idx*3+1);
			if(!rv) continue;
			order[idx]=i;
			return 1;
		}
	}
	return 0;
}

void init(int T) {
	int i, j, k, l, idx=0, A[7];
	for(i=1; i<=6; i++){
		for(j=i+1; j<=6; j++){
			for(k=j+1; k<=6; k++){
				Q[idx].type=1, Q[idx].a=i, Q[idx].b=j, Q[idx++].c=k;
				Q[idx].type=2, Q[idx].a=i, Q[idx].b=j, Q[idx++].c=k;
				Q[idx].type=3, Q[idx].a=i, Q[idx].b=j, Q[idx++].c=k;
				for(l=1; l<=6; l++) if(l!=i && l!=j && l!=k){
					Q[idx].type=4, Q[idx].a=i, Q[idx].b=j, Q[idx].c=k, Q[idx++].d=l;
				}
			}
		}
	}
	idx=0;
	for(i=1; i<=6; i++) A[i]=i;
	do{
		for(i=1; i<=6; i++) P[idx].A[i]=A[i];
		idx++;
	}while(next_permutation(A+1, A+7));
	vector<int> vec;
	for(i=0; i<MAXP; i++) vec.push_back(i);
	makeorder(0, vec, 1);
}

void orderCoins() {
	int i, idx=1, rv;
	for(i=0; i<6; i++){
		if(Q[order[idx]].type==1)
			rv=getLightest(Q[order[idx]].a, Q[order[idx]].b, Q[order[idx]].c);
		else if(Q[order[idx]].type==2)
			rv=getHeaviest(Q[order[idx]].a, Q[order[idx]].b, Q[order[idx]].c);
		else if(Q[order[idx]].type==3)
			rv=getMedian(Q[order[idx]].a, Q[order[idx]].b, Q[order[idx]].c);
		else
			rv=getNextLightest(Q[order[idx]].a, Q[order[idx]].b, Q[order[idx]].c, Q[order[idx]].d);
		if(rv==Q[order[idx]].a) rv=0;
		else if(rv==Q[order[idx]].b) rv=1;
		else rv=2;
		if(rv==0) idx=idx*3-1;
		else if(rv==1) idx=idx*3;
		else idx=idx*3+1;
	}
	idx=order[idx];
	int ans[6];
	for(i=1; i<=6; i++){
		ans[P[idx].A[i]-1]=i;
	}
	answer(ans);
}

Compilation message (stderr)

scales.cpp: In function 'int makeorder(int, std::vector<int>, int)':
scales.cpp:65:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0; j<list.size(); j++){
             ^
scales.cpp:74:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0; j<list.size(); j++){
              ^
scales.cpp: At global scope:
scales.cpp:94:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^

• Subtask 1: 100 / 100