Submission #49873

#	Time	Username	Problem	Language	Result	Execution time	Memory
49873		imeimi2000	Scales (IOI15_scales)	C++17	100 / 100	21 ms	944 KiB

scales

#include "scales.h"
#include <algorithm>
#include <vector>

using namespace std;

struct _qs {
    int i, a, b, c, d;
    int query() const {
        if (i == 1) return getHeaviest(a + 1, b + 1, c + 1) - 1;
        if (i == 2) return getLightest(a + 1, b + 1, c + 1) - 1;
        if (i == 3) return getMedian(a + 1, b + 1, c + 1) - 1;
        return getNextLightest(a + 1, b + 1, c + 1, d + 1) - 1;
    }
    int queryIdx() const {
        int x = query();
        if (x == a) return 1;
        if (x == b) return 2;
        return 3;
    }
} qs[120];

struct arr {
    int x[6];
    int query1(int a, int b, int c) const {
        int t = a;
        if (x[t] < x[b]) t = b;
        if (x[t] < x[c]) t = c;
        return t;
    }
    int query2(int a, int b, int c) const {
        int t = a;
        if (x[b] < x[t]) t = b;
        if (x[c] < x[t]) t = c;
        return t;
    }
    int query3(int a, int b, int c) const {
        return a + b + c - query1(a, b, c) - query2(a, b, c);
    }
    int query4(int a, int b, int c, int d) const {
        vector<int> vt;
        if (x[d] < x[a]) vt.push_back(a);
        if (x[d] < x[b]) vt.push_back(b);
        if (x[d] < x[c]) vt.push_back(c);
        if (vt.empty()) return query2(a, b, c);
        int t = vt[0];
        for (int i = 1; i < vt.size(); ++i) {
            if (x[vt[i]] < x[t]) t = vt[i];
        }
        return t;
    }
    int query(int i, int a, int b, int c, int d) const {
        if (i == 1) return query1(a, b, c);
        if (i == 2) return query2(a, b, c);
        if (i == 3) return query3(a, b, c);
        return query4(a, b, c, d);
    }
    int query(_qs q) const {
        return query(q.i, q.a, q.b, q.c, q.d);
    }
    int queryIdx(_qs q) const {
        int x = query(q);
        if (x == q.a) return 1;
        if (x == q.b) return 2;
        return 3;
    }
} as[720];

int ans[720][120];

int pow3[6];
int op[364];

bool dfs(int node, int dep, const vector<int> &vt) {
    if (dep == 0) return 1;
    for (int i = 0; i < 120; ++i) {
        vector<int> v[4];
        for (int j : vt) {
            v[ans[j][i]].push_back(j);
        }
        int mx = 0;
        for (int j = 1; j <= 3; ++j) {
            mx = max(mx, (int)v[j].size());
        }
        if (pow3[dep - 1] < mx) continue;
        int p = 1;
        for (int j = 1; j <= 3; ++j) {
            if (v[j].empty()) continue;
            if (!dfs(3 * node + j, dep - 1, v[j])){
                p = 0;
                break;
            }
        }
        if (p) {
            op[node] = i;
            return 1;
        }
    }
    return 0;
}

void init(int T) {
    pow3[0] = 1;
    for (int i = 1; i < 6; ++i) pow3[i] = 3 * pow3[i - 1];
    
    int p = 0;
    for (int i = 0; i < 6; ++i) {
        for (int j = i + 1; j < 6; ++j) {
            for (int k = j + 1; k < 6; ++k) {
                for (int t = 1; t <= 3; ++t) {
                    qs[p++] = { t, i, j, k, -1 };
                }
            }
        }
    }
    
    for (int i = 0; i < 6; ++i) {
        for (int j = i + 1; j < 6; ++j) {
            for (int k = j + 1; k < 6; ++k) {
                for (int t = 0; t < 6; ++t) {
                    if (i == t || j == t || k == t) continue;
                    qs[p++] = { 4, i, j, k, t };
                }
            }
        }
    }
        
    for (int i = 0; i < 6; ++i) as[0].x[i] = i;
    for (int i = 0; i < 720; ++i) {
        if (i) {
            for (int j = 0; j < 6; ++j) as[i].x[j] = as[i - 1].x[j];
            next_permutation(as[i].x, as[i].x + 6);
        }
        for (int j = 0; j < 120; ++j) {
            ans[i][j] = as[i].queryIdx(qs[j]);
        }
    }
    vector<int> in;
    for (int i = 0; i < 720; ++i) in.push_back(i);
    if (!dfs(0, 6, in)) throw -1;
}

void orderCoins() {
    int node = 0;
    vector<int> in;
    for (int i = 0; i < 720; ++i) in.push_back(i);
    while (in.size() > 1) {
        int x = op[node];
        int ret = qs[x].queryIdx();
        vector<int> tp;
        for (int j : in) {
            if (ans[j][x] == ret) tp.push_back(j);
        }
        node = 3 * node + ret;
        in = tp;
    }
    int ret[6];
    for (int i = 0; i < 6; ++i) ret[as[in[0]].x[i]] = i + 1;
    answer(ret);
}

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 member function 'int arr::query4(int, int, int, int) const':
scales.cpp:47:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 1; i < vt.size(); ++i) {
                         ~~^~~~~~~~~~~
scales.cpp: In member function 'int arr::queryIdx(_qs) const':
scales.cpp:62:13: warning: declaration of 'x' shadows a member of 'arr' [-Wshadow]
         int x = query(q);
             ^
scales.cpp:24:12: note: shadowed declaration is here
     int x[6];
            ^
scales.cpp: In function 'void init(int)':
scales.cpp:102:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^

• Subtask 1: 100 / 100