Submission #639855

#	Time	Username	Problem	Language	Result	Execution time	Memory
639855		piOOE	Scales (IOI15_scales)	C++17	39.02 / 100	1 ms	340 KiB

scales

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

using namespace std;

void init(int T) {

}

constexpr int n = 6;

vector<int> g[n + 1];

bool e[n + 1][n + 1], sm[n + 1][n + 1];

int cmp(int a, int b) {
    if (!e[a][b]) {
        return -1;  
    }
}

void add(int a, int b) {
    e[a][b] = e[b][a] = true;
    sm[a][b] = true;
    g[a].push_back(b);
    for (int i = 1; i <= n; ++i) {
        vector<bool> used(n + 1);
        function<void(int)> dfs = [&](int v) {
            e[i][v] = e[v][i] = true;
            used[v] = true;
            for (int to: g[v]) {
                if (!used[to]) {
                    dfs(to);
                }
            }
        };
        dfs(i);
    }
}

int myHeaviest(int a, int b, int c) {
    int x = getHeaviest(a, b, c);
    if (x != a) {
        add(x, a);
    }
    if (x != b) {
        add(x, b);
    }
    if (x != c) {
        add(x, c);
    }
    return x;
}

int myLightest(int a, int b, int c) {
    int x = getLightest(a, b, c);
    if (x != a) {
        add(a, x);
    }
    if (x != b) {
        add(b, x);
    }
    if (x != c) {
        add(c, x);
    }
    return x;
}

void ord(int a[]) {
    int x = myHeaviest(a[0], a[1], a[2]);
    int y = getMedian(a[0], a[1], a[2]);
    int z = a[0] + a[1] + a[2] - x - y;
    add(y, z);
    a[0] = x, a[1] = y, a[2] = z;
}

int p[n], a[3], b[3], ans[3], idx[3];

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

void orderCoins() {
    for (int i = 1; i <= n; ++i) g[i].clear();
    memset(e, 0, sizeof(e));
    memset(sm, 0, sizeof(sm));
    int tmp[6]{6, 5, 2, 3, 1, 4};
    shuffle(tmp, tmp + 6, rnd);
    for (int i = 0; i < 3; ++i) {
        a[i] = tmp[i];
        b[i] = tmp[i + 3];
    }
    ord(a);
    for (int i = 0; i < 3; ++i) {
        ans[i] = getNextLightest(a[0], a[1], a[2], b[i]);
        idx[i] = ans[i] == a[0] ? 0 : ans[i] == a[1] ? 1 : 2;
    }
    for (int i = 0; i < 3; ++i) {
        if (idx[i] != 2) {
            for (int j = 0; j <= idx[i]; ++j) {
                add(a[j], b[i]);
            }
            for (int j = idx[i] + 1; j < 3; ++j) {
                add(b[i], a[j]);
            }
        } else if (!e[a[idx[i]]][b[i]]) {
            while (true) {
                int j = 0;
                while (j < 3 && (j == i || e[b[j]][b[i]])) ++j;
                if (j != 3) {
                    int l = myLightest(a[idx[i]], b[i], b[j]);
                    if (l == b[j]) {
                        continue;
                    } else if (l == a[idx[i]]) {
                        add(b[i], a[0]);
                        add(b[i], a[1]);
                        add(b[i], a[2]);
                        break;
                    } else {
                        break;
                    }
                } else {
                    int l = myLightest(a[idx[i]], a[0], b[i]);
                    if (l != b[i]) {
                        add(b[i], a[0]);
                        add(b[i], a[1]);
                        add(b[i], a[2]);
                    }
                    break;
                }
            }
        } else if (sm[b[i]][a[2]]) {
            add(b[i], a[0]);
            add(b[i], a[1]);
            add(b[i], a[2]);
        }
    }
    bool lol = false;
    for (int i = 0; i < 3 && !lol; ++i) {
        for (int j = i + 1; j < 3 && !lol; ++j) {
            if (!e[b[i]][b[j]]) {
                ord(b);
                lol = true;
            }
        }
    }
    vector<bool> used(n + 1);
    vector<int> tops;
    function<void(int)> dfs = [&](int v) {
        used[v] = true;
        for (int to: g[v]) {
            if (!used[to]) {
                dfs(to);
            }
        }
        tops.push_back(v);
    };
    for (int i = 1; i <= n; ++i) {
        if (!used[i]) {
            dfs(i);
        }
    }
    answer(tops.data());
}

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) {
      |           ~~~~^
scales.cpp: In function 'int cmp(int, int)':
scales.cpp:20:1: warning: control reaches end of non-void function [-Wreturn-type]
   20 | }
      | ^

• Subtask 1: 39.022436 / 100