Submission #807460

#TimeUsernameProblemLanguageResultExecution timeMemory
807460FatihSolakScales (IOI15_scales)C++17
0 / 100
36 ms696 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...