Submission #520534

#	Time	Username	Problem	Language	Result	Execution time	Memory
520534		silverfish	Scales (IOI15_scales)	C++17	100 / 100	36 ms	484 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ar array
const int INF = 10000000;

int nextl(int a, int b, int c, int d, vector<int> &ind) {
    int al = 1;    
    a--; b--; c--; d--;
    if (ind[a] > ind[d] || ind[b] > ind[d] || ind[c] > ind[d]) al = 0;
    if (al == 1) {
        if (ind[a] < ind[b] && ind[a] < ind[c])return a + 1;
        if (ind[b] < ind[a] && ind[b] < ind[c])return b + 1;
        return c + 1;
    }
    if (ind[a] > ind[d])
        if ((ind[a] < ind[b] || ind[b] < ind[d]) && (ind[a] < ind[c]||ind[c]<ind[d]))return a + 1;
    if(ind[b] > ind[d])
        if((ind[b]<ind[a]||ind[a]<ind[d])&&(ind[b]<ind[c]||ind[c]<ind[d]))return b + 1;
    return c + 1;
}
int mid(int a, int b, int c, vector<int> &ind) {
    a--; b--; c--;
    if (ind[b] < ind[a] && ind[a] < ind[c])return a + 1;
    if (ind[c] < ind[a] && ind[a] < ind[b])return a + 1;
    if (ind[a] < ind[b] && ind[b] < ind[c])return b + 1;
    if (ind[c] < ind[b] && ind[b] < ind[a])return b + 1;
    return c + 1;
}
int heavy(int a, int b, int c, vector<int> &ind) {
    a--; b--; c--;
    if (ind[a] > ind[b] && ind[a] > ind[c])return a + 1;
    if (ind[b] > ind[a] && ind[b] > ind[c])return b + 1;
    return c + 1;
}
int light(int a, int b, int c, vector<int> &ind) {
    a--; b--; c--;
    if(ind[a]<ind[b]&&ind[a]<ind[c]) return a + 1;
    if(ind[b]<ind[a]&&ind[b]<ind[c]) return b + 1;
    return c + 1;
}

struct query{
	// 1 : nextl
	// 2 : light
	// 3 : mid
	// 4 : heavy
	int t;
	int a, b, c, d;

	int execute(int cp){
		vector<int> p(6), ind(6);
		for(int i = 5; i >= 0; --i) p[i]=(cp%10), cp/=10;
		for(int i = 0; i < 6; ++i) ind[p[i]-1] = i;

		switch(t){
			case 1:
				return nextl(a,b,c,d,ind);
			case 2:
				return light(a,b,c,ind);
			case 3:
				return mid(a,b,c,ind);
			case 4:
				return heavy(a,b,c,ind);
		}
		return -1;
	}

	int execute_real(){
		switch(t){
			case 1:
				return getNextLightest(a,b,c,d);
			case 2:
				return getLightest(a,b,c);
			case 3:
				return getMedian(a,b,c);
			case 4:
				return getHeaviest(a,b,c);
		}
		return -1;
	}
};

struct node{
	query cur;
	ar<node*, 7> nxt;
	int ansp=0;
};

int mxd = 0, first;
vector<query> allq;

void solve(node* rt, vector<int> p, int d){
	if(p.size() == 1){
		mxd = max(mxd, d);
		rt->ansp = p[0];
		return;
	}

	if(d == 0) rt->cur = allq[first];
	else{
		int mn = INF;
		query best;
		for(auto q : allq){
			int cnt[7] = {0};
			for(int cp : p) ++cnt[q.execute(cp)];
			int mx = 0;
			for(int i = 1; i <= 6; ++i) mx = max(mx, cnt[i]);	
			if(mx < mn){
				mn = mx;
				best = q;
			}
		}
		rt->cur = best;
	}

	vector<int> np[7];
	for(int cp : p) np[rt->cur.execute(cp)].pb(cp);
	for(int i = 1; i <= 6; ++i){
		if(np[i].size()){
			rt->nxt[i] = new node;
			solve(rt->nxt[i], np[i], d+1);
		}else rt->nxt[i] = nullptr;
	}
}


vector<int> allp;
node* rt = new node;

void gen_all(){
	for(int i=1;i<=6;++i) for(int j=i+1;j<=6;++j)
	for(int k=j+1;k<=6;++k){
		allq.pb({2,i,j,k});
		allq.pb({3,i,j,k});
		allq.pb({4,i,j,k});
	}
	
	for(int i = 1; i <= 6; ++i) for(int j = 1; j <= 6; ++j){
		if(j==i) continue;
		for(int k = j+1; k <= 6; ++k){
			if(k==i) continue;
			for(int a = k+1; a <= 6; ++a){
				if(a==i) continue;
				allq.pb({1,i,j,k,a});
			}
		}
	}
	vector<int> p = {1,2,3,4,5,6};
	do{
		int v=0, mul = 1;
		for(int i = 5; i >= 0; --i){
			v += p[i]*mul;
			mul *= 10;
		}
		allp.pb(v);
	}while(next_permutation(p.begin(), p.end()));

	return;
}

void init(int T) {
	gen_all();
	int mn = INF, mnpos=0;
	first = 1;
	solve(rt, allp, 0);
	//cout << mxd << '\n';
	return;
}
 
void orderCoins() {
	node* crt = rt;

	while(!crt->ansp){
		int v = crt->cur.execute_real();
		crt = crt->nxt[v];
	}

	int ans[6], cp = crt->ansp;
	for(int i = 5; i >= 0; --i) ans[i]=(cp%10), cp/=10;
	answer(ans);
	return;
}

Compilation message (stderr)

scales.cpp: In function 'void gen_all()':
scales.cpp:135:20: warning: missing initializer for member 'query::d' [-Wmissing-field-initializers]
  135 |   allq.pb({2,i,j,k});
      |                    ^
scales.cpp:136:20: warning: missing initializer for member 'query::d' [-Wmissing-field-initializers]
  136 |   allq.pb({3,i,j,k});
      |                    ^
scales.cpp:137:20: warning: missing initializer for member 'query::d' [-Wmissing-field-initializers]
  137 |   allq.pb({4,i,j,k});
      |                    ^
scales.cpp: In function 'void init(int)':
scales.cpp:165:6: warning: unused variable 'mn' [-Wunused-variable]
  165 |  int mn = INF, mnpos=0;
      |      ^~
scales.cpp:165:16: warning: unused variable 'mnpos' [-Wunused-variable]
  165 |  int mn = INF, mnpos=0;
      |                ^~~~~
scales.cpp:163:15: warning: unused parameter 'T' [-Wunused-parameter]
  163 | void init(int T) {
      |           ~~~~^

• Subtask 1: 100 / 100