Submission #669212

#	Time	Username	Problem	Language	Result	Execution time	Memory
669212		alvingogo	Scales (IOI15_scales)	C++14	100 / 100	117 ms	624 KiB

scales

#include <bits/stdc++.h>
#include "scales.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

int dfs(vector<int>& x,int s);
map<vector<int>,array<int,4> > mp;
int po[7]={1,3,9,27,81,243,729};
vector<vector<int> > z;
int get(vector<int> g,int a,int b,int c,int t){
    if(t==-1){
        for(int i=0;i<6;i++){
            if(g[i]==a || g[i]==b || g[i]==c){
                return g[i];
            }
        }
    }
    else if(t==-2){
        for(int i=5;i>=0;i--){
            if(g[i]==a || g[i]==b || g[i]==c){
                return g[i];
            }
        }
    }
    else if(t==-3){
        int cnt=0;
        for(int i=0;i<6;i++){
            if(g[i]==a || g[i]==b || g[i]==c){
                cnt++;
            }
            if(cnt==2){
                return g[i];
            }
        }
    }
    else{
        int cnt=0;
        for(int i=0;i<6;i++){
            if(g[i]==t){
                cnt++;
            }
            if(cnt && (g[i]==a || g[i]==b || g[i]==c)){
                return g[i];
            }
        }
        return get(g,a,b,c,-1);
    }
}
int fg(int a,int b,int c){
    return getHeaviest(a+1,b+1,c+1)-1;
}
int fm(int a,int b,int c){
    return getMedian(a+1,b+1,c+1)-1;
}
int fl(int a,int b,int c){
    return getLightest(a+1,b+1,c+1)-1;
}
int nx(int a,int b,int c,int d){
    return getNextLightest(a+1,b+1,c+1,d+1)-1;
}
inline int cal(vector<int>& x,int t,int i,int j,int k,int s){
    vector<int> b,c,d;
    for(auto y:x){
        auto h=z[y];
        int a=get(h,i,j,k,t);
        if(a==i){
            b.push_back(y);
        }
        else if(a==j){
            c.push_back(y);
        }
        else{
            d.push_back(y);
        }
    }
    if(b.size()>po[s-1] || c.size()>po[s-1] || d.size()>po[s-1]){
        return 0;
    }
    if(dfs(b,s-1) && dfs(c,s-1) && dfs(d,s-1)){
        return 1;
    }
    return 0;
}
int dfs(vector<int>& x,int s){
    if(s<0 || x.size()>po[s]){
        return 0;
    }
    else if(mp.find(x)!=mp.end()){
        if(mp[x][0]==-1){
            return 0;
        }
        else{
            return 1;
        }
    }
    else if(s==0){
        return 1;
    }
    for(int i=0;i<4;i++){
        for(int j=i+1;j<5;j++){
            for(int k=j+1;k<6;k++){
                for(int t=-3;t<6;t++){
                    if(t!=i && t!=j && t!=k){
                        if(cal(x,t,i,j,k,s)){
                            mp[x]={i,j,k,t};
                            return 1;
                        }
                    }
                }
            }
        }
    }
    mp[x]={-1,-1,-1,-1};
    return 0;
}
void init(int T){
    vector<int> g(6);
    iota(g.begin(),g.end(),0);
    for(int i=0;i<720;i++){
        z.push_back(g);
        next_permutation(g.begin(),g.end());
    }
    vector<int> k(720);
    iota(k.begin(),k.end(),0);
    dfs(k,6);
}
void orderCoins(){
    vector<int> g(720);
    iota(g.begin(),g.end(),0);
    while(g.size()>1){
        auto h=mp[g];
        vector<int> nw;
        int y;
        if(h[3]==-1){
            y=fl(h[0],h[1],h[2]);
        }
        else if(h[3]==-3){
            y=fm(h[0],h[1],h[2]);
        }
        else if(h[3]==-2){
            y=fg(h[0],h[1],h[2]);
        }
        else{
            y=nx(h[0],h[1],h[2],h[3]);
        }
        for(auto r:g){
            if(get(z[r],h[0],h[1],h[2],h[3])==y){
                nw.push_back(r);
            }
        }
        g=nw;
    }
    int ans[6];
    for(int i=0;i<6;i++){
        ans[i]=z[g[0]][i]+1;
    }
    answer(ans);
}

Compilation message (stderr)

scales.cpp: In function 'int cal(std::vector<int>&, int, int, int, int, int)':
scales.cpp:80:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |     if(b.size()>po[s-1] || c.size()>po[s-1] || d.size()>po[s-1]){
      |        ~~~~~~~~^~~~~~~~
scales.cpp:80:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |     if(b.size()>po[s-1] || c.size()>po[s-1] || d.size()>po[s-1]){
      |                            ~~~~~~~~^~~~~~~~
scales.cpp:80:56: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |     if(b.size()>po[s-1] || c.size()>po[s-1] || d.size()>po[s-1]){
      |                                                ~~~~~~~~^~~~~~~~
scales.cpp: In function 'int dfs(std::vector<int>&, int)':
scales.cpp:89:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |     if(s<0 || x.size()>po[s]){
      |               ~~~~~~~~^~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:120:15: warning: unused parameter 'T' [-Wunused-parameter]
  120 | void init(int T){
      |           ~~~~^
scales.cpp: In function 'int get(std::vector<int>, int, int, int, int)':
scales.cpp:52:1: warning: control reaches end of non-void function [-Wreturn-type]
   52 | }
      | ^

• Subtask 1: 100 / 100