Submission #388767

#	Time	Username	Problem	Language	Result	Execution time	Memory
388767		alishahali1382	Scales (IOI15_scales)	C++14	100 / 100	87 ms	1220 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
typedef array<bool, 720> state;

int n, m;
vi perms[720];
vi opers[120];
int tmp[7], out[6], tav[7];
bool mark[720];
int prep[720][120];
map<state, int> DP[7];
state all1, curr;

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;
}
bool BT(state st, int cnt){
	int t1=0;
	for (int j=0; j<720; j++) t1+=st[j];
	// debug2(cnt, t1)
	if (t1<=1) return 1;
	if (t1>tav[cnt]) return 0;
	if (DP[cnt].count(st)) return (DP[cnt][st]!=-1);
	for (int i=0; i<120; i++){
		int ta=0, tb=0, tc=0;
		int a=opers[i][1], b=opers[i][2], c=opers[i][3];
		state Sa, Sb, Sc;
		for (int j=0; j<720; j++) Sa[j]=Sb[j]=Sc[j]=0;
		for (int j=0; j<720; j++) if (st[j]){
			int tmp=prep[j][i];
			if (tmp==a) ta++, Sa[j]=1;
			if (tmp==b) tb++, Sb[j]=1;
			if (tmp==c) tc++, Sc[j]=1;
		}
		if (max({ta, tb, tc})>tav[cnt-1]) continue ;
		if (BT(Sa, cnt-1) && BT(Sb, cnt-1) && BT(Sc, cnt-1)){
			DP[cnt][st]=i;
			return 1;
		}
	}
	DP[cnt][st]=-1;
	return 0;
}

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]);
	for (int i=0; i<720; i++) all1[i]=1;
	tav[0]=1;
	for (int i=1; i<=6; i++) tav[i]=tav[i-1]*3;
	assert(BT(all1, 6));
}

void orderCoins(){
	curr=all1;
	for (int cnt=6; cnt; cnt--){
		int opid=DP[cnt][curr];
		assert(opid!=-1);
		int res=Ask(opers[opid]), ted=0;
		for (int i=0; i<n; i++) if (curr[i]){
			if (prep[i][opid]==res) ted++;
			else curr[i]=0;
		}
		if (ted==1) break ;
	}
	for (int i=0; i<n; i++) if (curr[i]){
		for (int j=0; j<6; j++) out[j]=perms[i][j];
	}
	answer(out);
	// debug("done")
}

Compilation message (stderr)

scales.cpp: In function 'bool BT(state, int)':
scales.cpp:56:8: warning: declaration of 'tmp' shadows a global declaration [-Wshadow]
   56 |    int tmp=prep[j][i];
      |        ^~~
scales.cpp:19:5: note: shadowed declaration is here
   19 | int tmp[7], out[6], tav[7];
      |     ^~~

• Subtask 1: 100 / 100