Submission #386751

#	Time	Username	Problem	Language	Result	Execution time	Memory
386751		alishahali1382	Scales (IOI15_scales)	C++14	72.02 / 100	27 ms	876 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<"="<<x<<", "<<y<<"\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define all(x) x.begin(), x.end()
#define pb push_back

int n, m;
vi perms[720];
vi opers[120];
int tmp[7], out[6];
bool mark[720];
int prep[720][120];

int Ask(vi &oper){
	if (oper[0]==1) return getLightest(oper[1], oper[2], oper[3]);
	if (oper[0]==2) return getMedian(oper[1], oper[2], oper[3]);
	if (oper[0]==3) return getHeaviest(oper[1], oper[2], oper[3]);
	return getNextLightest(oper[1], oper[2], oper[3], oper[4]);
}
int _Ask(vi &perm, vi oper){
	for (int i=0; i<6; i++) tmp[perm[i]]=i;
	sort(oper.begin()+1, oper.begin()+4, [](int i, int j){
		return tmp[i]<tmp[j];
	});
	if (oper[0]<=3) return oper[oper[0]];
	int a=oper[1], b=oper[2], c=oper[3], d=oper[4];
	if (tmp[d]<tmp[a]) return a;
	if (tmp[d]<tmp[b]) return b;
	if (tmp[d]<tmp[c]) return c;
	return a;
}

void init(int T){
	T=T; // dont warn :)
	vi shit={1, 2, 3, 4, 5, 6};
	do{
		perms[n++]=shit;
	} while(next_permutation(all(shit)));

	for (int a=1; a<=6; a++) for (int b=a+1; b<=6; b++) for (int c=b+1; c<=6; c++){
		opers[m++]={1, a, b, c};
		opers[m++]={2, a, b, c};
		opers[m++]={3, a, b, c};
		for (int d=1; d<=6; d++) if (d!=a && d!=b && d!=c) opers[m++]={4, a, b, c, d};
	}
	assert(n==720 && m==120);
	for (int i=0; i<n; i++) for (int j=0; j<m; j++)
		prep[i][j]=_Ask(perms[i], opers[j]);

}

void orderCoins(){
	memset(mark, 1, sizeof(mark));
	while (1){
		int bst=100000, opid=-1;
		for (int i=0; i<m; i++){
			int a=opers[i][1], b=opers[i][2], c=opers[i][3];
			int ta=0, tb=0, tc=0;
			for (int j=0; j<n; j++) if (mark[j]){
				ta+=(prep[j][i]==a);
				tb+=(prep[j][i]==b);
				tc+=(prep[j][i]==c);
			}
			int val=max({ta, tb, tc});
			if (val<bst || opid==-1){
				bst=val;
				opid=i;
			}
		}
		assert(opid!=-1);
		int res=Ask(opers[opid]), ted=0;
		for (int i=0; i<n; i++) if (mark[i]){
			if (prep[i][opid]==res) ted++;
			else mark[i]=0;
		}
		// debug2(bst, ted)
		if (ted==1) break ;
	}
	for (int i=0; i<n; i++) if (mark[i]){
		for (int j=0; j<6; j++) out[j]=perms[i][j];
	}
	answer(out);
	// debug("done")
}

• Subtask 1: 72.02381 / 100