Submission #520355

#	Time	Username	Problem	Language	Result	Execution time	Memory
520355		silverfish	Scales (IOI15_scales)	C++17	56.42 / 100	5 ms	548 KiB

scales

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

int ind[6];
map<int, ar<int,6>> ans;

int nextl(int a, int b, int c, int d) {
    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) {
    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) {
    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) {
    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;
}

void init(int T) {
	vector<vector<int>> q;
	q.pb({0, 6, 5, 1, 2});
	q.pb({0, 5, 4, 6, 1});
	q.pb({0, 5, 6, 2, 4});
	q.pb({0, 6, 2, 1, 3});
	q.pb({1,1,2,3});
	q.pb({0, 5, 6, 4, 3});
	q.pb({1,4,5,6});
	q.pb({1,3,4,5});
	map<int,int> cnt;
	for(int i = 0; i < 8; ++i){
		vector<int> p = {1, 2, 3, 4, 5, 6};
		do{
			for(int i = 0; i < 6; ++i) ind[p[i]-1] = i;
			vector<int> cans;
			for(int j = 0; j <= i; ++j){
				if(q[j][0]){
					cans.pb(mid(q[j][1], q[j][2], q[j][3]));	
				}else{
					cans.pb(nextl(q[j][1], q[j][2], q[j][3], q[j][4]));
				}
			}

			int mul = 1, cur = 0;
			for(int x : cans){
				cur += mul*x;	
				mul *= 10;
			}
			++cnt[cur];
			if(cnt[cur] > 1){
				ans[cur][0] = 0;
			}else{
				for(int k = 0; k < 6; ++k){
					ans[cur][k] = p[k];
				}
			}
		}while(next_permutation(p.begin(), p.end()));
	}
	/*
	cout << cnt[46246651] << '\n';
	int mx = 0, mxpos;
	for(auto [x, c] : cnt){
		if(c > mx){
			mx = c;
			mxpos = x;
		}
	}
	cout << mx << ' ' << mxpos << '\n';
	*/
	return;
}
 
void orderCoins() {
	int w[6];
	vector<int> q;
	int mul = 1, cur = 0;
	cur += mul*getNextLightest(6,5,1,2);
	mul *= 10;
	if(ans[cur][0] != 0){
		for(int i = 0; i < 6; ++i) w[i] = ans[cur][i];
		answer(w);
		return;
	}
	cur += mul*(getNextLightest(5,4,6,1));
	mul *= 10;
	if(ans[cur][0] != 0){
		for(int i = 0; i < 6; ++i) w[i] = ans[cur][i];
		answer(w);
		return;
	}
	cur += mul*(getNextLightest(5,6,2,4));
	mul *= 10;
	if(ans[cur][0] != 0){
		for(int i = 0; i < 6; ++i) w[i] = ans[cur][i];
		answer(w);
		return;
	}
	cur += mul*(getNextLightest(6,2,1,3));
	mul *= 10;
	if(ans[cur][0] != 0){
		for(int i = 0; i < 6; ++i) w[i] = ans[cur][i];
		answer(w);
		return;
	}
	cur += mul*(getMedian(1,2,3));
	mul *= 10;
	if(ans[cur][0] != 0){
		for(int i = 0; i < 6; ++i) w[i] = ans[cur][i];
		answer(w);
		return;
	}
	cur += mul*(getNextLightest(5,6,4,3));
	mul *= 10;
	if(ans[cur][0] != 0){
		for(int i = 0; i < 6; ++i) w[i] = ans[cur][i];
		answer(w);
		return;
	}
	cur += mul*(getMedian(4,5,6));
	mul *= 10;
	if(ans[cur][0] != 0){
		for(int i = 0; i < 6; ++i) w[i] = ans[cur][i];
		answer(w);
		return;
	}
	cur += mul*(getMedian(3,4,5));
	mul *= 10;
//	cout << cur << '\n';
//	cout << ans[cur][0] << '\n';
	if(ans[cur][0] != 0){
		for(int i = 0; i < 6; ++i) w[i] = ans[cur][i];
		answer(w);
		return;
	}
	return;
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:97:12: warning: declaration of 'i' shadows a previous local [-Wshadow]
   97 |    for(int i = 0; i < 6; ++i) ind[p[i]-1] = i;
      |            ^
scales.cpp:94:10: note: shadowed declaration is here
   94 |  for(int i = 0; i < 8; ++i){
      |          ^
scales.cpp:83:15: warning: unused parameter 'T' [-Wunused-parameter]
   83 | void init(int T) {
      |           ~~~~^

• Subtask 1: 56.423611 / 100