Submission #1013454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013454		d4xn	Scales (IOI15_scales)	C++17	71.43 / 100	1 ms	600 KiB

scales

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

const int N = 6;

mt19937 rng(time(nullptr) + 769);

int c[N], ans[N];

void init(int T) {
    for (int i = 0; i < N; i++) {
        c[i] = i+1;
    }
    shuffle(c, c+N, rng);
}

void orderCoins() {
    shuffle(c, c+N, rng);

    vector<int> L;
    int x = getLightest(c[0], c[1], c[2]);
    int z = getHeaviest(c[0], c[1], c[2]);

    int y = c[0];
    if (y == x || y == z) y = c[1];
    if (y == x || y == z) y = c[2];

    L.push_back(x);
    L.push_back(y);
    L.push_back(z);

    //cerr << L[0] << " " << L[1] << " " << L[2] << endl;

    y = getMedian(c[3], c[4], c[5]);
    
    x = c[3];
    if (x == y) x = c[4];
    
    z = c[4];
    if (z == y || z == x) z = c[5];

    deque<int> q;
    while (!L.empty()) {
        //cerr << L.back() << " " << x << " " << z << endl;
        int mx = getHeaviest(L.back(), x, z);
        q.push_front(mx);
        if (mx == L.back()) {
            L.pop_back();
        }
        else {
            if (mx == x) x = z;
            break;
        }
    }

    if (L.size() == 3) {//cerr << "3" << endl;
        L.push_back(q[0]);

        vector<int> R;
        R.push_back(x);
        R.push_back(y);

        x = getNextLightest(L[3], L[2], L[1], R[1]);

        if (x == L[1]) {
            x = getMedian(L[0], R[0], R[1]);

            if (x == L[0]) {
                L.insert(L.begin()+1, R[1]);
                L.insert(L.begin(), R[0]);
            }
            else if (x == R[0]) {
                L.insert(L.begin()+1, R[1]);
                L.insert(L.begin()+1, R[0]);
            }
            else {
                L.insert(L.begin(), R[1]);
                L.insert(L.begin(), R[0]);
            }
        }
        else {
            int idx = 1;
            while (x != L[idx]) idx++;

            L.insert(L.begin() + idx, R[1]);
            //R.pop_back();

            if (R[1] == L[3]) {
                x = getNextLightest(L[3], L[2], L[1], R[0]);

                if (x == L[1]) {
                    x = getLightest(L[0], R[0], L[1]);
                    if (x == R[0]) {
                        L.insert(L.begin(), R[0]);
                    }
                    else {
                        L.insert(L.begin()+1, R[0]);
                    }
                    R.pop_back();
                }
                else {
                    idx = 1;
                    while (x != L[idx]) idx++;

                    L.insert(L.begin() + idx, R[0]);
                    R.pop_back();
                }
            }
            else {
                x = getNextLightest(L[2], L[1], L[0], R[0]);
                
                idx = 0;
                while (x != L[idx]) idx++;

                L.insert(L.begin() + idx, R[0]);
            }
        }

        for (int i = 0; i < N; i++) {
            ans[i] = L[i];
            //cerr << ans[i] << " ";
        }//cerr << "a" << endl;

        answer(ans);
        return;
    }
    else if (L.size() == 2) {//cerr << "2" << endl;
        int mx = getHeaviest(x, y, L[1]);
        q.push_front(mx);

        if (mx == L[1]) {
            int med = getMedian(x, y, L[0]);
            if (med == x) {
                q.push_front(y);
                q.push_front(x);
                q.push_front(L[0]);                
            }
            else if (med == y) {
                q.push_front(L[0]);
                q.push_front(y);
                q.push_front(x); 
            }
            else {
                q.push_front(y);
                q.push_front(L[0]);
                q.push_front(x); 
            }
        }
        else {
            // mx = y
            int med = getMedian(x, L[0], L[1]);
            if (med == x) {
                q.push_front(L[1]);
                q.push_front(x);
                q.push_front(L[0]);                
            }
            else if (med == L[0]) {
                q.push_front(L[1]);
                q.push_front(L[0]);
                q.push_front(x); 
            }
            else {
                q.push_front(x);
                q.push_front(L[1]);
                q.push_front(L[0]); 
            }
        }
    }
    else if (L.size() == 1) {//cerr << "1" << endl;
        int med = getMedian(x, y, L[0]);
        //cerr << x << " " << y << " " << L[0] << endl;
        if (med == x) {
                q.push_front(y);
                q.push_front(x);
                q.push_front(L[0]);                
            }
            else if (med == y) {
                q.push_front(L[0]);
                q.push_front(y);
                q.push_front(x); 
            }
            else {
                q.push_front(y);
                q.push_front(L[0]);
                q.push_front(x); 
            }
    }
    else {//cerr << "0" << endl;
        int mx = getHeaviest(x, y, z);
        if (mx == x) {
            q.push_front(x);
            q.push_front(y);
            q.push_front(z);
        }
        else {
            q.push_front(z);
            q.push_front(y);
            q.push_front(x);
        }
    }

    for (int i = 0; i < N; i++) {
        ans[i] = q[i];
        //cerr << ans[i] << " ";
    }//cerr << "b" << endl;

    answer(ans);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:11:15: warning: unused parameter 'T' [-Wunused-parameter]
   11 | void init(int T) {
      |           ~~~~^

• Subtask 1: 71.428571 / 100