Submission #807460

# Submission time Handle Problem Language Result Execution time Memory
807460 2023-08-04T17:48:26 Z FatihSolak Scales (IOI15_scales) C++17
0 / 100
36 ms 696 KB
#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);
      |                       ^
# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 596 KB Hacked.
2 Incorrect 29 ms 588 KB Hacked.
3 Incorrect 28 ms 596 KB Hacked.
4 Incorrect 29 ms 620 KB Hacked.
5 Incorrect 29 ms 600 KB Hacked.
6 Incorrect 29 ms 596 KB Hacked.
7 Incorrect 29 ms 640 KB Hacked.
8 Incorrect 29 ms 612 KB Hacked.
9 Incorrect 36 ms 608 KB Hacked.
10 Incorrect 29 ms 584 KB Hacked.
11 Incorrect 29 ms 596 KB Hacked.
12 Incorrect 29 ms 596 KB Hacked.
13 Incorrect 29 ms 632 KB Hacked.
14 Incorrect 29 ms 648 KB Hacked.
15 Incorrect 29 ms 600 KB Hacked.
16 Incorrect 34 ms 576 KB Hacked.
17 Incorrect 36 ms 696 KB Hacked.
18 Incorrect 29 ms 636 KB Hacked.
19 Incorrect 29 ms 624 KB Hacked.
20 Incorrect 28 ms 596 KB Hacked.
21 Incorrect 28 ms 596 KB Hacked.
22 Incorrect 29 ms 596 KB Hacked.
23 Incorrect 29 ms 560 KB Hacked.
24 Incorrect 29 ms 596 KB Hacked.
25 Incorrect 29 ms 596 KB Hacked.
26 Incorrect 28 ms 596 KB Hacked.
27 Incorrect 29 ms 648 KB Hacked.
28 Incorrect 29 ms 616 KB Hacked.
29 Incorrect 29 ms 592 KB Hacked.
30 Incorrect 29 ms 616 KB Hacked.
31 Incorrect 28 ms 588 KB Hacked.
32 Incorrect 29 ms 604 KB Hacked.
33 Incorrect 29 ms 612 KB Hacked.
34 Incorrect 36 ms 648 KB Hacked.
35 Incorrect 29 ms 596 KB Hacked.
36 Incorrect 29 ms 612 KB Hacked.
37 Incorrect 28 ms 608 KB Hacked.
38 Incorrect 28 ms 596 KB Hacked.
39 Incorrect 29 ms 628 KB Hacked.
40 Incorrect 29 ms 596 KB Hacked.