Submission #807442

#	Time	Username	Problem	Language	Result	Execution time	Memory
807442		FatihSolak	Scales (IOI15_scales)	C++17	76.49 / 100	39 ms	712 KiB

scales

#include "scales.h"
#define K 2000
#include <bits/stdc++.h>
using namespace std;
vector<int> opp[K];
vector<int> ans[K];
int to[K][7];
int cnt[7];
int timer = 2;
int get(int op,int a,int b,int c,int d,vector<int> &v){
    vector<int> id(6,0);
    for(int i = 0;i<6;i++){
        id[v[i]-1] = i;
    }
    a--,b--,c--,d--;
    if(id[a] > id[b])
        swap(a,b);
    if(id[a] > id[c])
        swap(a,c);
    if(id[b] > id[c])
        swap(b,c);
    if(op == 1){
        return b + 1;
    }
    if(op == 2){
        return c + 1;
    }
    if(op == 3){
        return a + 1;
    }
    if(op == 4){
        if(id[a] > id[d])
            return a + 1;
        if(id[b] > id[d])
            return b + 1;
        if(id[c] > id[d])
            return c + 1;
        return a + 1;        
    }
}
void go(int x,vector<vector<int>> v){
    //cout << x << ' ' << v.size() << endl;
    if(v.size() == 0)
        return;
    if(v.size() == 1){
        ans[x] = v[0]; 
        return;
    }
    int val = 1e9;
    for(int op = 1;op<=4;op++){
        for(int a = 1;a<=6;a++){
            for(int b = a+1;b<=6;b++){
                for(int c = b+1;c<=6;c++){
                    if(op == 4){
                        for(int d = 1;d<=6;d++){
                            if(a == d || b == d || c == d)
                                continue;
                            for(auto u:v){
                                cnt[get(op,a,b,c,d,u)]++;
                            }
                            int mini = 1e9;
                            int maxi = 0;
                            for(int i = 1;i<=6;i++){
                                if(i != a && i != b && i != c)continue;
                                mini = min(mini,cnt[i]);
                                maxi = max(maxi,cnt[i]);
                                cnt[i] = 0;
                            }
                            if(maxi - mini < val){
                                val = maxi - mini;
                                opp[x] = {op,a,b,c,d};
                            }
                        }
                    }
                    else{
                        for(auto u:v){
                            cnt[get(op,a,b,c,-1,u)]++;
                        }
                        int mini = 1e9;
                        int maxi = 0;
                        for(int i = 1;i<=6;i++){
                            if(i != a && i != b && i != c)continue;
                            mini = min(mini,cnt[i]);
                            maxi = max(maxi,cnt[i]);
                            cnt[i] = 0;
                        }
                        if(maxi - mini < val){
                            val = maxi - mini;
                            opp[x] = {op,a,b,c};
                        }
                    }
                }
            }
        }
    }
    vector<vector<int>> cnt2[7];
    for(auto u:v){
        int d = -1;
        if(opp[x].size() > 4)
            d = opp[x][4];
        cnt2[get(opp[x][0],opp[x][1],opp[x][2],opp[x][3],d,u)].push_back(u);
    }
    for(int i = 1;i<=6;i++){
        if(i != opp[x][1] && i != opp[x][2] && i != opp[x][3])
            continue;
        to[x][i] = timer++;
        go(to[x][i],cnt2[i]);
    }
}
void init(int T) {
    vector<vector<int>> a;
    vector<int> x = {1,2,3,4,5,6};
    do{
        a.push_back(x);
    }while(next_permutation(x.begin(),x.end()));
    go(1,a);
}

void orderCoins(){
    int now = 1;
    while(ans[now].empty()){
        int op = opp[now][0];
        int a = opp[now][1];
        int b = opp[now][2];
        int c = opp[now][3];
        int d = -1;
        if(op == 4)
            d = opp[now][4];
        int val = -1;
        if(op == 1){
            val = getMedian(a,b,c);
        }
        if(op == 2){
            val = getHeaviest(a,b,c);
        }
        if(op == 3){
            val = getLightest(a,b,c);
        }
        if(op == 4){
            val = getNextLightest(a,b,c,d);
        }
        now = to[now][val];
    }
    int W[] = {ans[now][0],ans[now][1],ans[now][2],ans[now][3],ans[now][4],ans[now][5]};
    answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:110:15: warning: unused parameter 'T' [-Wunused-parameter]
  110 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'int get(int, int, int, int, int, std::vector<int>&)':
scales.cpp:11:23: warning: control reaches end of non-void function [-Wreturn-type]
   11 |     vector<int> id(6,0);
      |                       ^

• Subtask 1: 76.488095 / 100