Submission #64533

#	Time	Username	Problem	Language	Result	Execution time	Memory
64533		KieranHorgan	Scales (IOI15_scales)	C++17	72.02 / 100	506 ms	796 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 || (curVal==bestVal && rand()%5 == 0))
                        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 || (curVal==bestVal && rand()%5 == 0))
                        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 || (curVal==bestVal && rand()%5 == 0))
                        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 || (curVal==bestVal && rand()%5 == 0))
                                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: 72.02381 / 100