Submission #1038720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038720		shenfe1	Scales (IOI15_scales)	C++17	0 / 100	219 ms	864 KiB

scales

#include <bits/stdc++.h>
#include "scales.h"

#pragma GCC optimize("Ofast")

#define ll long long
#define pb push_back
#define sz(s) (int)s.size()
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define F first
#define S second

using namespace std;

const int L=6;

map<vector<vector<int>>,pii> mp;
map<vector<vector<int>>,pair<pii,pii>> qr;
int pos[7];

bool check(int i,int j,int k,int d,vector<int> x){
    for(int j=0;j<6;j++)pos[x[j]]=j;
    if(pos[i]<pos[d]){
        if(pos[i]<min(pos[j],pos[k])&&max(pos[j],pos[k])<pos[d])return 1;
    }
    else{
        if(!(pos[d]<=pos[j]&&pos[j]<=pos[i])&&!(pos[d]<=pos[k]&&pos[k]<=pos[i]))return 1;
    }
    return 0;
}

int solve(vector<vector<int>> vec,int pot,int lev){
    if(sz(vec)<=1)return 0;
    if(mp.count(vec))return mp[vec].F;
    pii res={100,0};
    {
        for(int i=1;i<=L;i++){
            for(int j=i+1;j<=L;j++){
                for(int k=j+1;k<=L;k++){
                    vector<vector<int>> a,b,c;
                    for(auto x:vec){
                        for(int f=0;f<L;f++)pos[x[f]]=f;
                        if(pos[i]<=pos[j]&&pos[i]<=pos[k])a.pb(x);
                        else if(pos[j]<=pos[i]&&pos[j]<=pos[k])b.pb(x);
                        else c.pb(x);
                    }
                    if(max({sz(a),sz(b),sz(c)})>pot/3||max({sz(a),sz(b),sz(c)})==sz(vec))continue;
                    int cur=max({solve(a,pot/3,lev+1),solve(b,pot/3,lev+1),solve(c,pot/3,lev+1)})+1;
                    if(cur==6-lev){
                        mp[vec]={cur,0};
                        qr[vec]={{i,j},{k,0}};
                        return 6-lev;
                    }
                }
            }
        }
    }
    {
        for(int i=1;i<=L;i++){
            for(int j=i+1;j<=L;j++){
                for(int k=j+1;k<=L;k++){
                    vector<vector<int>> a,b,c;
                    for(auto x:vec){
                        for(int f=0;f<L;f++)pos[x[f]]=f;
                        if(min(pos[j],pos[k])<pos[i]&&pos[i]<max(pos[j],pos[k]))a.pb(x);
                        else if(min(pos[i],pos[k])<pos[j]&&pos[j]<max(pos[i],pos[k]))b.pb(x);
                        else c.pb(x);
                    }
                    if(max({sz(a),sz(b),sz(c)})>pot/3||max({sz(a),sz(b),sz(c)})==sz(vec))continue;
                    int cur=max({solve(a,pot/3,lev+1),solve(b,pot/3,lev+1),solve(c,pot/3,lev+1)})+1;
                    if(cur==6-lev){
                        mp[vec]={cur,1};
                        qr[vec]={{i,j},{k,0}};
                        return 6-lev;
                    }
                }
            }
        }        
    }
    {
        for(int i=1;i<=L;i++){
            for(int j=i+1;j<=L;j++){
                for(int k=j+1;k<=L;k++){
                    vector<vector<int>> a,b,c;
                    for(auto x:vec){
                        for(int f=0;f<L;f++)pos[x[f]]=f;
                        if(pos[i]>=pos[j]&&pos[i]>=pos[k])a.pb(x);
                        else if(pos[j]>=pos[i]&&pos[j]>=pos[k])b.pb(x);
                        else c.pb(x);
                    }
                    if(max({sz(a),sz(b),sz(c)})>pot/3||max({sz(a),sz(b),sz(c)})==sz(vec))continue;
                    int cur=max({solve(a,pot/3,lev+1),solve(b,pot/3,lev+1),solve(c,pot/3,lev+1)})+1;
                    if(cur==6-lev){
                        mp[vec]={cur,2};
                        qr[vec]={{i,j},{k,0}};
                        return 6-lev;
                    }
                }
            }
        }
    }
    {
        for(int i=1;i<=L;i++){
            assert(i<=L);
            for(int j=i+1;j<=L;j++){
                if(i>L){
                    cout<<i<<"\n";
                    exit(0);
                }
                assert(i<=L&&j<=L);
                for(int k=j+1;k<=L;k++){
                    assert(i<=L&&j<=L&&k<=L);
                    for(int d=1;d<=L;d++){
                        if(i==d||j==d||k==d)continue;
                        assert(d<=6);
                        assert(i<=6&&j<=6&&d<=6);
                        vector<vector<int>> a,b,c;
                        for(auto x:vec){
                            if(check(i,j,k,d,x))a.pb(x);
                            else if(check(j,i,k,d,x))b.pb(x);
                            else c.pb(x);
                        }
                        if(max({sz(a),sz(b),sz(c)})>pot/3||max({sz(a),sz(b),sz(c)})==sz(vec))continue;
                        assert(sz(a)+sz(b)+sz(c)==sz(vec));
                        int cur=max({solve(a,pot/3,lev+1),solve(b,pot/3,lev+1),solve(c,pot/3,lev+1)})+1;
                        if(cur==6-lev){
                            mp[vec]={cur,3};
                            qr[vec]={{i,j},{k,d}};
                            return 6-lev;
                        }
                    }
                }
            }
        }
    }
}

void init(int T){
    vector<int> v;
    for(int i=1;i<=L;i++)v.pb(i);
    vector<vector<int>> vec;
    do{
        vec.pb(v);
    }while(next_permutation(all(v)));
    solve(vec,729,0);
}

void orderCoins(){
    vector<int> v;
    for(int i=1;i<=L;i++)v.pb(i);
    vector<vector<int>> vec;
    do{
        vec.pb(v);
    }while(next_permutation(all(v)));
    while(sz(vec)>1){
        int zap=mp[vec].S;
        int res;
        pair<pii,int> query={qr[vec].F,qr[vec].S.F};
        if(zap==0){
            res=getLightest(query.F.F,query.F.S,query.S);
            vector<vector<int>> nw;
            for(auto x:vec){
                int pos[7];
                for(int j=0;j<6;j++)pos[x[j]]=j;
                if(pos[res]<=min({pos[query.F.F],pos[query.F.S],pos[query.S]}))nw.pb(x);
            }
            swap(nw,vec);
        }
        else if(zap==1){
            res=getMedian(query.F.F,query.F.S,query.S);
            vector<vector<int>> nw;
            for(auto x:vec){
                int pos[7];
                for(int j=0;j<6;j++)pos[x[j]]=j;
                if(pos[res]>min({pos[query.F.F],pos[query.F.S],pos[query.S]})&&pos[res]<max({pos[query.F.F],pos[query.F.S],pos[query.S]}))nw.pb(x);
            }
            swap(nw,vec);
        }
        else if(zap==2){
            res=getHeaviest(query.F.F,query.F.S,query.S);
            vector<vector<int>> nw;
            for(auto x:vec){
                int pos[7];
                for(int j=0;j<6;j++)pos[x[j]]=j;
                if(pos[res]>=max({pos[query.F.F],pos[query.F.S],pos[query.S]}))nw.pb(x);
            }
            swap(nw,vec);
        }
        else{
            
            res=getNextLightest(query.F.F,query.F.S,query.S,qr[vec].S.S);
            vector<vector<int>> nw;
            for(auto x:vec){
                int pos[7];
                for(int j=0;j<6;j++)pos[x[j]]=j;
                int P=pos[qr[vec].S.S];
                if(pos[res]<P){
                    if(pos[res]<=min({pos[query.F.F],pos[query.F.S],pos[query.S]})&&max({pos[query.F.F],pos[query.F.S],pos[query.S]})<P){
                        nw.pb(x);
                    }
                }
                else{
                    if(!(P<pos[query.F.F]&&pos[query.F.F]<pos[res])&&!(P<pos[query.F.S]&&pos[query.F.S]<pos[res])&&!(P<pos[query.S]&&pos[query.S]<pos[res]))nw.pb(x);
                }
            }
            swap(nw,vec);      
        }
    }
    int C[6];
    for(int i=0;i<6;i++)C[i]=vec[0][i];
    answer(C);
}

Compilation message (stderr)

scales.cpp: In function 'bool check(int, int, int, int, std::vector<int>)':
scales.cpp:23:13: warning: declaration of 'int j' shadows a parameter [-Wshadow]
   23 |     for(int j=0;j<6;j++)pos[x[j]]=j;
      |             ^
scales.cpp:22:22: note: shadowed declaration is here
   22 | bool check(int i,int j,int k,int d,vector<int> x){
      |                  ~~~~^
scales.cpp: In function 'int solve(std::vector<std::vector<int> >, int, int)':
scales.cpp:36:9: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   36 |     pii res={100,0};
      |         ^~~
scales.cpp: In function 'void init(int)':
scales.cpp:139:15: warning: unused parameter 'T' [-Wunused-parameter]
  139 | void init(int T){
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:164:21: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
  164 |                 int pos[7];
      |                     ^~~
scales.cpp:20:5: note: shadowed declaration is here
   20 | int pos[7];
      |     ^~~
scales.cpp:174:21: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
  174 |                 int pos[7];
      |                     ^~~
scales.cpp:20:5: note: shadowed declaration is here
   20 | int pos[7];
      |     ^~~
scales.cpp:184:21: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
  184 |                 int pos[7];
      |                     ^~~
scales.cpp:20:5: note: shadowed declaration is here
   20 | int pos[7];
      |     ^~~
scales.cpp:195:21: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
  195 |                 int pos[7];
      |                     ^~~
scales.cpp:20:5: note: shadowed declaration is here
   20 | int pos[7];
      |     ^~~
scales.cpp: In function 'int solve(std::vector<std::vector<int> >, int, int)':
scales.cpp:137:1: warning: control reaches end of non-void function [-Wreturn-type]
  137 | }
      | ^

• Subtask 1: 0 / 100