Submission #60067

#	Time	Username	Problem	Language	Result	Execution time	Memory
60067		KieranHorgan	Scales (IOI15_scales)	C++17	71.43 / 100	543 ms	812 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;

void init(int T) {
    /* ... */
}

int gH(vector<int> v, int A, int B, int C) {
	--A;--B;--C;
	int H = max(v[A], max(v[B], v[C]));
	if(v[A]==H) return ++A;
	if(v[B]==H) return ++B;
	return ++C;
}
int gL(vector<int> v, int A, int B, int C) {
	--A;--B;--C;
	int L = min(v[A], min(v[B], v[C]));
	if(v[A]==L) return ++A;
	if(v[B]==L) return ++B;
	return ++C;
}
int gM(vector<int> v, int A, int B, int C) {
	--A;--B;--C;
	int H = max(v[A], max(v[B], v[C]));
	if(v[A]==H) {
		if(v[B] > v[C]) return ++B;
		else			return ++C;
	}
	if(v[B]==H) {
		if(v[A] > v[C]) return ++A;
		else			return ++C;
	}
	if(v[B] > v[A]) return ++B;
	return ++A;
}
int gNL(vector<int> v, int A, int B, int C, int D) {
	--A;--B;--C;--D;
	vector<pair<int, int>> vp;
	if(v[A] > v[D]) vp.push_back({v[A], A+1});
	if(v[B] > v[D]) vp.push_back({v[B], B+1});
	if(v[C] > v[D]) vp.push_back({v[C], C+1});
	if(vp.empty()) return gL(v, ++A, ++B, ++C);
	sort(vp.begin(), vp.end());
	return vp[0].second;
}

int a[7];
void orderCoins() {
    /* ... */
    // int W[] = {1, 2, 3, 4, 5, 6};
    // answer(W);

    vector<vector<int>> pos;
    vector<vector<int>> nextPos;
    vector<int> perm = {1, 2, 3, 4, 5, 6};
    do {
    	pos.push_back(perm);
    } while(next_permutation(perm.begin(), perm.end()));


    while(pos.size() > 1) {
    	int best = 0;
    	int bestVal = 1000;
    	for(int A = 1; A <= 6; A++) {
	    	for(int B = A+1; B <= 6; B++) {
		    	for(int C = B+1; C <= 6; C++) {
		    		int cur, curVal;

		    		cur = 1*10000 + A*1000 + B*100 + C*10 + 0*1;
		    		memset(a, 0, sizeof(a));
		    		for(auto v: pos)
		    			a[gH(v, A, B, C)]++;
		    		curVal = max(a[A], max(a[B], a[C]));
		    		if(curVal < bestVal)
		    			bestVal=curVal, best=cur;

		    		cur = 2*10000 + A*1000 + B*100 + C*10 + 0*1;
		    		memset(a, 0, sizeof(a));
		    		for(auto v: pos)
		    			a[gL(v, A, B, C)]++;
		    		curVal = max(a[A], max(a[B], a[C]));
		    		if(curVal < bestVal)
		    			bestVal=curVal, best=cur;

		    		cur = 3*10000 + A*1000 + B*100 + C*10 + 0*1;
		    		memset(a, 0, sizeof(a));
		    		for(auto v: pos)
		    			a[gM(v, A, B, C)]++;
		    		curVal = max(a[A], max(a[B], a[C]));
		    		if(curVal < bestVal)
		    			bestVal=curVal, best=cur;

		    		for(int D = 1; D <= 6; D++)
		    			if(D != A && D != B && D != C) {
				    		memset(a, 0, sizeof(a));
				    		cur = 4*10000 + A*1000 + B*100 + C*10 + D*1;
				    		for(auto v: pos)
				    			a[gNL(v, A, B, C, D)]++;
				    		curVal = max(a[A], max(a[B], a[C]));
				    		if(curVal < bestVal)
				    			bestVal=curVal, best=cur;
		    			}
		    	}
		    }
    	}

    	// cerr << best << " " << bestVal << endl;

    	int t, A, B, C, D;
    	D = best%10; best/=10;
    	C = best%10; best/=10;
    	B = best%10; best/=10;
    	A = best%10; best/=10;
    	t = best%10; best/=10;

    	int val;
    	if(t==1) {
    		val = getHeaviest(A,B,C);
    		for(auto v: pos)
    			if(gH(v, A, B, C) == val)
    				nextPos.push_back(v);
    	} else if(t==2) {
    		val = getLightest(A,B,C);
    		for(auto v: pos)
    			if(gL(v, A, B, C) == val)
    				nextPos.push_back(v);
    	} else if(t==3) {
    		val = getMedian(A,B,C);
    		for(auto v: pos)
    			if(gM(v, A, B, C) == val)
    				nextPos.push_back(v);
    	} else {
    		val = getNextLightest(A,B,C,D);
    		for(auto v: pos)
    			if(gNL(v, A, B, C, D) == val)
    				nextPos.push_back(v);
		}

		swap(pos, nextPos);
		nextPos.clear();
    }
    int ans[] = {0,0,0,0,0,0};
    for(int i = 0; i < 6; i++) {
    	ans[pos[0][i]-1] = i+1;
    }
    answer(ans);
}

Compilation message (stderr)

In file included from grader.c:2:0:
graderlib.c: In function 'void answer(int*)':
graderlib.c:53:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (_ghksjhdfkae19ga_ > 1) 
     ^~
graderlib.c:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  for (i = 0; i < 6; i++) {
  ^~~
scales.cpp: In function 'void init(int)':
scales.cpp:5:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^

• Subtask 1: 71.428571 / 100