Submission #807461

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
807461	2023-08-04T17:48:45 Z	FatihSolak	Scales (IOI15_scales)	C++17	71.4286 / 100	36 ms	664 KB

scales

#include "scales.h"
#define K 2000
#include <bits/stdc++.h>
using namespace std;
vector<int> opp[K];
vector<int> ans[K];
int d[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){
        //cout << d[x] << endl;
        ans[x] = v[0]; 
        return;
    }
    int val = 1e9;
    for(int op:{1,4,2,3}){
        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 < val){
                            val = maxi;
                            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++;
        d[to[x][i]] = d[x] + 1;
        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

scales.cpp: In function 'int get(int, int, int, int, int, std::vector<int>&)':
scales.cpp:11:38: warning: declaration of 'd' shadows a global declaration [-Wshadow]
   11 | int get(int op,int a,int b,int c,int d,vector<int> &v){
      |                                  ~~~~^
scales.cpp:7:5: note: shadowed declaration is here
    7 | int d[K];
      |     ^
scales.cpp: In function 'void go(int, std::vector<std::vector<int> >)':
scales.cpp:57:33: warning: declaration of 'd' shadows a global declaration [-Wshadow]
   57 |                         for(int d = 1;d<=6;d++){
      |                                 ^
scales.cpp:7:5: note: shadowed declaration is here
    7 | int d[K];
      |     ^
scales.cpp:100:13: warning: declaration of 'd' shadows a global declaration [-Wshadow]
  100 |         int d = -1;
      |             ^
scales.cpp:7:5: note: shadowed declaration is here
    7 | int d[K];
      |     ^
scales.cpp: In function 'void init(int)':
scales.cpp:113:15: warning: unused parameter 'T' [-Wunused-parameter]
  113 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:129:13: warning: declaration of 'd' shadows a global declaration [-Wshadow]
  129 |         int d = -1;
      |             ^
scales.cpp:7:5: note: shadowed declaration is here
    7 | int d[K];
      |     ^
scales.cpp: In function 'int get(int, int, int, int, int, std::vector<int>&)':
scales.cpp:12:23: warning: control reaches end of non-void function [-Wreturn-type]
   12 |     vector<int> id(6,0);
      |                       ^

Subtask #1

71.428571 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	36 ms	624 KB	Output is partially correct
2	Partially correct	29 ms	596 KB	Output is partially correct
3	Partially correct	28 ms	616 KB	Output is partially correct
4	Partially correct	28 ms	604 KB	Output is partially correct
5	Partially correct	28 ms	612 KB	Output is partially correct
6	Partially correct	28 ms	604 KB	Output is partially correct
7	Partially correct	28 ms	624 KB	Output is partially correct
8	Partially correct	28 ms	596 KB	Output is partially correct
9	Partially correct	28 ms	636 KB	Output is partially correct
10	Partially correct	28 ms	600 KB	Output is partially correct
11	Partially correct	29 ms	620 KB	Output is partially correct
12	Partially correct	28 ms	596 KB	Output is partially correct
13	Partially correct	28 ms	616 KB	Output is partially correct
14	Partially correct	28 ms	632 KB	Output is partially correct
15	Partially correct	28 ms	596 KB	Output is partially correct
16	Partially correct	28 ms	648 KB	Output is partially correct
17	Partially correct	30 ms	620 KB	Output is partially correct
18	Partially correct	31 ms	596 KB	Output is partially correct
19	Partially correct	28 ms	616 KB	Output is partially correct
20	Partially correct	32 ms	580 KB	Output is partially correct
21	Partially correct	35 ms	624 KB	Output is partially correct
22	Partially correct	28 ms	604 KB	Output is partially correct
23	Partially correct	29 ms	636 KB	Output is partially correct
24	Partially correct	28 ms	636 KB	Output is partially correct
25	Partially correct	29 ms	596 KB	Output is partially correct
26	Partially correct	29 ms	584 KB	Output is partially correct
27	Partially correct	28 ms	624 KB	Output is partially correct
28	Partially correct	28 ms	584 KB	Output is partially correct
29	Partially correct	28 ms	588 KB	Output is partially correct
30	Partially correct	30 ms	628 KB	Output is partially correct
31	Partially correct	28 ms	596 KB	Output is partially correct
32	Partially correct	35 ms	664 KB	Output is partially correct
33	Partially correct	29 ms	612 KB	Output is partially correct
34	Partially correct	28 ms	572 KB	Output is partially correct
35	Partially correct	28 ms	616 KB	Output is partially correct
36	Partially correct	28 ms	596 KB	Output is partially correct
37	Partially correct	28 ms	596 KB	Output is partially correct
38	Partially correct	30 ms	584 KB	Output is partially correct
39	Partially correct	28 ms	624 KB	Output is partially correct
40	Partially correct	28 ms	636 KB	Output is partially correct