Submission #424145

#	Time	Username	Problem	Language	Result	Execution time	Memory
424145		InternetPerson10	Scales (IOI15_scales)	C++17	72.92 / 100	57 ms	324 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>

using namespace std;

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

bool good[720];
int l[20][3], h[20][3], m[20][3], g[60][3];
vector<int> v = {1, 2, 3, 4, 5, 6}, v2 = {1, 2, 3, 4, 5, 6};

void answer(int W[]);

int lightest(int a, int b, int c) {
    int x = v[a], y = v[b], z = v[c];
    int ans = min(x, min(y, z));
    if(ans == x) return a;
    if(ans == y) return b;
    if(ans == z) return c;
    return 69;
}

int heaviest(int a, int b, int c) {
    int x = v[a], y = v[b], z = v[c];
    int ans = max(x, max(y, z));
    if(ans == x) return a;
    if(ans == y) return b;
    if(ans == z) return c;
    return 69;
}

int mediaest(int a, int b, int c) {
    int x = v[a], y = v[b], z = v[c];
    int ans = x + y + z - min(x, min(y, z)) - max(x, max(y, z));
    if(ans == x) return a;
    if(ans == y) return b;
    if(ans == z) return c;
    return 69;
}

int getnext(int a, int b, int c, int d) {
    int x = v[a], y = v[b], z = v[c], w = v[d];
    if(w > x && w > y && w > z) return lightest(a, b, c);
    if(w < x && w < y && w < z) return lightest(a, b, c);
    if(w > v[mediaest(a, b, c)]) return heaviest(a, b, c);
    return mediaest(a, b, c);
}

void orderCoins() {
    for(int i = 0; i < 720; i++) good[i] = true;
    for(int z = 0; z < 7; z++) {
        int ggg = -1;
        for(int y = 0; y < 3; y++) {
            for(int k = 0; k < 20; k++) l[k][y] = h[k][y] = m[k][y] = g[k][y] = 0;
            for(int k = 20; k < 60; k++) g[k][y] = 0;
        }
        do {
            ggg++;
            if(!good[ggg]) continue;
            // cout << ggg << ' ';
            int y = 0;
            for(int i = 0; i < 4; i++) {
                for(int j = i+1; j < 5; j++) {
                    for(int k = j+1; k < 6; k++) {
                        int ll = lightest(i, j, k);
                        if(ll == i) l[y][0]++;
                        if(ll == j) l[y][1]++;
                        if(ll == k) l[y][2]++;
                        int hh = heaviest(i, j, k);
                        if(hh == i) h[y][0]++;
                        if(hh == j) h[y][1]++;
                        if(hh == k) h[y][2]++;
                        int mm = mediaest(i, j, k);
                        if(mm == i) m[y][0]++;
                        if(mm == j) m[y][1]++;
                        if(mm == k) m[y][2]++;
                        int x = 0;
                        for(int w = 0; w < 6; w++) {
                            if(w == i || w == j || w == k) continue;
                            int gg = getnext(i, j, k, w);
                            if(gg == i) g[3*y+x][0]++;
                            if(gg == j) g[3*y+x][1]++;
                            if(gg == k) g[3*y+x][2]++;
                            x++;
                        }
                        y++;
                    }
                }
            }
        } while(next_permutation(v.begin(), v.end()));
        // cout << '\n';
        int best = 999, thebest = -1;
        for(int i = 0; i < 20; i++) {
            int ll = max(l[i][0], max(l[i][1], l[i][2]));
            if(ll <= best) {
                best = ll;
                thebest = i;
            }
        }
        for(int i = 0; i < 20; i++) {
            int hh = max(h[i][0], max(h[i][1], h[i][2]));
            if(hh <= best) {
                best = hh;
                thebest = 20+i;
            }
        }
        for(int i = 0; i < 20; i++) {
            int mm = max(m[i][0], max(m[i][1], m[i][2]));
            if(mm <= best) {
                best = mm;
                thebest = 40+i;
            }
        }
        for(int i = 0; i < 60; i++) {
            int gg = max(g[i][0], max(g[i][1], g[i][2]));
            if(gg <= best) {
                best = gg;
                thebest = 60 + i;
            }
        }
        // cout << best << ' ' << thebest << '\n';
        if(thebest < 20) {
            ggg = 0;
            for(int i = 0; i < 4; i++) {
                for(int j = i+1; j < 5; j++) {
                    for(int k = j+1; k < 6; k++) {
                        if(ggg == thebest) {
                            v.swap(v2);
                            int ax = getLightest(i+1, j+1, k+1) - 1, gg = -1;
                            // cout << "Ax " << ax << '\n';
                            do {
                                gg++;
                                if(!good[gg]) continue;
                                if(lightest(i, j, k) == ax) good[gg] = true;
                                else {
                                    // cout << "Yeeting " << gg << ": " << v[i] << ' ' << v[j] << ' ' << v[k] << '\n';
                                    good[gg] = false;
                                }
                            } while(next_permutation(v.begin(), v.end()));
                            v.swap(v2);
                        }
                        ggg++;
                        // cout << "Gee " << ggg << '\n';
                    }
                }
            }
        }
        else if(thebest < 40) {
            thebest -= 20;
            ggg = 0;
            for(int i = 0; i < 4; i++) {
                for(int j = i+1; j < 5; j++) {
                    for(int k = j+1; k < 6; k++) {
                        if(ggg == thebest) {
                            v.swap(v2);
                            int ax = getHeaviest(i+1, j+1, k+1) - 1, gg = -1;
                            do {
                                gg++;
                                if(!good[gg]) continue;
                                if(heaviest(i, j, k) == ax) good[gg] = true;
                                else good[gg] = false;
                            } while(next_permutation(v.begin(), v.end()));
                            v.swap(v2);
                        }
                        ggg++;
                    }
                }
            }
        }
        else if(thebest < 60) {
            thebest -= 40;
            ggg = 0;
            for(int i = 0; i < 4; i++) {
                for(int j = i+1; j < 5; j++) {
                    for(int k = j+1; k < 6; k++) {
                        if(ggg == thebest) {
                            v.swap(v2);
                            int ax = getMedian(i+1, j+1, k+1) - 1, gg = -1;
                            do {
                                gg++;
                                if(!good[gg]) continue;
                                if(mediaest(i, j, k) == ax) good[gg] = true;
                                else good[gg] = false;
                            } while(next_permutation(v.begin(), v.end()));
                            v.swap(v2);
                        }
                        ggg++;
                    }
                }
            }
        }
        else {
            thebest -= 60;
            ggg = 0;
            for(int i = 0; i < 4; i++) {
                for(int j = i+1; j < 5; j++) {
                    for(int k = j+1; k < 6; k++) {
                        for(int w = 0; w < 6; w++) {
                            if(w == i || w == j || w == k) continue;
                            if(ggg == thebest) {
                                v.swap(v2);
                                int ax = getNextLightest(i+1, j+1, k+1, w+1) - 1, gg = -1;
                                do {
                                    gg++;
                                    if(!good[gg]) continue;
                                    if(getnext(i, j, k, w) == ax) good[gg] = true;
                                    else good[gg] = false;
                                } while(next_permutation(v.begin(), v.end()));
                                v.swap(v2);
                            }
                            ggg++;
                        }
                    }
                }
            }
        }
        int goods = 0;
        for(int i = 0; i < 720; i++) {
            if(good[i]) goods++;
        }
        if(goods == 1) break;
    }
    int W[] = {1, 2, 3, 4, 5, 6};
    int ggg = 0;
    do {
        if(good[ggg]) {
            for(int i = 0; i < 6; i++) W[v[i]-1] = i+1;
        }
        ggg++;
    } while(next_permutation(v.begin(), v.end()));
    answer(W);
}

Compilation message (stderr)

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

• Subtask 1: 72.916667 / 100