Submission #93879

#	Time	Username	Problem	Language	Result	Execution time	Memory
93879		cki86201	Scales (IOI15_scales)	C++11	100 / 100	478 ms	888 KiB

scales

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include "scales.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

vector <int> perms[730];
vector< vector <int> > el;
int qsave[150][730];

int get_query(vector <int> q, vector<int> r) {
    int cmd = q[0];
    int a[3] = {r[q[1]], r[q[2]], r[q[3]]};
    sort(a, a+3);
    if(cmd <= 3) {
        int val = a[1];
        if(cmd == 1) val = a[2];
        else if(cmd == 2) val = a[0];
        for(int i=1;i<=3;i++) if(r[q[i]] == val) return i - 1;
    }
    else {
        int val = -1;
        for(int i=0;i<3;i++) if(a[i] > r[q[4]]) {
            val = a[i]; break;
        }
        if(val == -1) val = a[0];
        for(int i=1;i<=3;i++) if(r[q[i]] == val) return i - 1;
    }
    return -1;
}

int callq(vector <int> q) {
    int r = -1;
    if(q[0] == 1) r = getHeaviest(q[1] + 1, q[2] + 1, q[3] + 1) - 1;
    else if(q[0] == 2) r = getLightest(q[1] + 1, q[2] + 1, q[3] + 1) - 1;
    else if(q[0] == 3) r = getMedian(q[1] + 1, q[2] + 1, q[3] + 1) - 1;
    else r = getNextLightest(q[1] + 1, q[2] + 1, q[3] + 1, q[4] + 1) - 1;
    for(int i=1;i<=3;i++) if(q[i] == r) return i-1;
    return -1;
}

void init(int T) {
    vector <int> v = {0,1,2,3,4,5};
    int c = 0;
    do {
        perms[c++] = v;
    } while(next_permutation(all(v)));
    rep(i,6) rep(j,i) rep(k,j) {
        rep(c,3) el.push_back({c+1, k, j, i});
        rep(u,6) if(u != i && u != j && u != k) el.push_back({4, k, j, i, u});
    }
    rep(i, 120) rep(j, 720) {
        qsave[i][j] = get_query(el[i], perms[j]);
    }
}

int get_next(const vector <int> &X) {
    int mn = 1e9;
    vector <int> ml;
    rep(i, 120) {
        int cnt[3] = {};
        for(int e : X) cnt[qsave[i][e]]++;
        sort(cnt, cnt+3);
        if(mn > cnt[2]) {
            mn = cnt[2]; ml.clear(); ml.pb(i);
        }
        else if(mn == cnt[2]) {
            ml.pb(i);
        }
    }
    if(mn == 1) return ml[0];
    mn = 1e9;
    int x = -1;
    for(int i : ml) {
        vector <int> W[3];
        for(int e : X) W[qsave[i][e]].pb(e);
        int cnt[3] = {};
        rep(k, 3) cnt[k] = 1e9;
        rep(k, 3) {
            rep(j, 120) {
                int r[3] = {};
                for(int f : W[k]) r[qsave[j][f]]++;
                sort(r,r+3);
                if(cnt[k] > r[2]) cnt[k] = r[2];
            }
        }
        sort(cnt, cnt+3);
        if(mn > cnt[2]) mn = cnt[2], x = i;
    }
    return x;
}

void fix(vector <int> &X, int cn, int ex) {
    vector <int> Y;
    for(int e : X) if(qsave[cn][e] == ex) Y.pb(e);
    X = Y;
}

void orderCoins() {
    vector <int> now;
    rep(i, 720) now.pb(i);
    while(szz(now) > 1) {
        int v = get_next(now);
        int a = callq(el[v]);
        fix(now, v, a);
    }
    int ans[6] = {};
    rep(i, 6) ans[perms[now[0]][i]] = i + 1;
    answer(ans);
}

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:73:13: warning: declaration of 'c' shadows a previous local [-Wshadow]
         rep(c,3) el.push_back({c+1, k, j, i});
             ^
scales.cpp:27:26: note: in definition of macro 'rep'
 #define rep(i,n) for(int i=0;i<n;i++)
                          ^
scales.cpp:68:9: note: shadowed declaration is here
     int c = 0;
         ^
scales.cpp:66:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^

• Subtask 1: 100 / 100