Submission #115418

#	Time	Username	Problem	Language	Result	Execution time	Memory
115418		nvmdava	Scales (IOI15_scales)	C++17	100 / 100	14 ms	768 KiB

scales

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

int depmax[] = {729, 243, 81, 27, 9, 3, 1};

struct Ord{
    int a[7];
    Ord(vector<int>& v){
        for(int i = 0; i < 6; i++)
            a[i + 1] = v[i];
    }
};

struct Query{
    int a, b, c, d;
    Query(int _a, int _b, int _c, int _d){
        a = _a;
        b = _b;
        c = _c;
        d = _d;
    }
    int ask(){
        int res;
        if(d == a) res = getLightest(a, b, c);
        else if(d == b) res = getMedian(a, b, c);
        else if(d == c) res = getHeaviest(a, b, c);
        else res = getNextLightest(a, b, c, d);
        if(res == a) return 1;
        if(res == b) return 2;
        if(res == c) return 3;
    }

    int simask(Ord& ord){
        int i = a, j = b, l = c, res;
        if(ord.a[i] > ord.a[j]) swap(i, j);
        if(ord.a[j] > ord.a[l]) swap(j, l);
        if(ord.a[i] > ord.a[j]) swap(i, j);
        if(a == d) res = i;
        else if(b == d) res = j;
        else if(c == d) res = l;
        else if(ord.a[d] < ord.a[i]) res = i;
        else if(ord.a[d] < ord.a[j]) res = j;
        else if(ord.a[d] < ord.a[l]) res = l;
        else res = i;
        if(res == a) return 1;
        if(res == b) return 2;
        if(res == c) return 3;
    }
};

vector<Query> lists;

struct Node{
    int dep;
    Query* q;
    vector<Ord*> pos;
    Node* go[4];

    bool init(){
        if(pos.size() <= 1) return 1;
        int cnt[4] = {0};
        bool ok = 0;
        for(auto& qq : lists){
            cnt[1] = 0;
            cnt[2] = 0;
            cnt[3] = 0;

            for(auto& ord : pos){
                int res = qq.simask(*ord);
                cnt[res]++;
                if(cnt[res] > depmax[dep]) break;
            }
            if(cnt[1] > depmax[dep]) continue;
            if(cnt[2] > depmax[dep]) continue;
            if(cnt[3] > depmax[dep]) continue;
            q = &qq;
            for(int i = 1; i <= 3; i++){
                go[i] = new Node();
                go[i] -> dep = dep + 1;
            }

            for(auto ord : pos){
                go[qq.simask(*ord)] -> pos.push_back(ord);
            }

            if(!go[1] -> init()){
                delete go[1];
                continue;
            }
            if(!go[2] -> init()){
                delete go[2];
                continue;
            }
            if(!go[3] -> init()){
                delete go[3];
                continue;
            }

            ok = 1;
            break;
        }
        return ok;
    }

} *root;

void create(){
    for(int i = 1; i < 5; i++){
        for(int j = i + 1; j < 6; j++){
            for(int l = j + 1; l <= 6; l++){
                for(int k = 1; k <= 6; k++){
                    lists.push_back(Query(i, j, l, k));
                }
            }
        }
    }
}

void init(int T) {
    create();
    root = new Node();
    vector<int> v = {1, 2, 3, 4, 5, 6};

    do{
        root -> pos.push_back(new Ord(v));
    } while(next_permutation(v.begin(), v.end()));
    root -> dep = 1;
    root -> init();
}

void orderCoins() {
    /* ... */
    int W[] = {1, 2, 3, 4, 5, 6};
    Node* ans = root;
    while(ans -> pos.size() != 1)
        ans = ans -> go[ans -> q -> ask()];
    for(int i = 1; i <= 6; i++){
        W[ans -> pos[0] -> a[i] - 1] = i;
    }
    answer(W);
}

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:120:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^
scales.cpp: In member function 'int Query::simask(Ord&)':
scales.cpp:49:5: warning: control reaches end of non-void function [-Wreturn-type]
     }
     ^
scales.cpp: In member function 'int Query::ask()':
scales.cpp:32:5: warning: control reaches end of non-void function [-Wreturn-type]
     }
     ^

• Subtask 1: 100 / 100