Submission #1038737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038737		shenfe1	Scales (IOI15_scales)	C++17	100 / 100	30 ms	1156 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;
}

bool check1(int i,int j,int k,int d,vector<int> x){
    for(int f=0;f<L;f++)pos[x[f]]=f;
    if(d==0&&pos[i]<=pos[j]&&pos[i]<=pos[k])return 1;
    if(d==1&&min(pos[j],pos[k])<pos[i]&&pos[i]<max(pos[j],pos[k]))return 1;
    if(d==2&&pos[i]>=pos[j]&&pos[i]>=pos[k])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 d=0;d<3;d++){
        for(int i=1;i<=L;i++){
            for(int j=i+1;j<=L;j++){
                for(int k=j+1;k<=L;k++){
                    assert(d<3&&i<=L&&j<=L&&k<=L);
                    vector<vector<int>> a,b,c;
                    for(auto x:vec){
                        if(check1(i,j,k,d,x))a.pb(x);
                        else if(check1(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;
                    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,d};
                        qr[vec]={{i,j},{k,d}};
                        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++){
                for(int d=1;d<=L;d++){
                    if(i==d||j==d||k==d)continue;
                    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;
                    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;
                    }
                }
            }
        }
    }
    return mp[vec].F;
}

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:44:9: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   44 |     pii res={100,0};
      |         ^~~
scales.cpp: In function 'void init(int)':
scales.cpp:92:15: warning: unused parameter 'T' [-Wunused-parameter]
   92 | void init(int T){
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:117:21: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
  117 |                 int pos[7];
      |                     ^~~
scales.cpp:20:5: note: shadowed declaration is here
   20 | int pos[7];
      |     ^~~
scales.cpp:127:21: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
  127 |                 int pos[7];
      |                     ^~~
scales.cpp:20:5: note: shadowed declaration is here
   20 | int pos[7];
      |     ^~~
scales.cpp:137:21: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
  137 |                 int pos[7];
      |                     ^~~
scales.cpp:20:5: note: shadowed declaration is here
   20 | int pos[7];
      |     ^~~
scales.cpp:148:21: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
  148 |                 int pos[7];
      |                     ^~~
scales.cpp:20:5: note: shadowed declaration is here
   20 | int pos[7];
      |     ^~~

• Subtask 1: 100 / 100