Submission #72994

#	Time	Username	Problem	Language	Result	Execution time	Memory
72994		edisonhello	Scales (IOI15_scales)	C++14	100 / 100	893 ms	892 KiB

scales

#include<bits/stdc++.h>
using namespace std;

#ifndef WEAK
#include"scales.h"
#else

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wreturn-type"
int coins[6],pos[6],qtime;
int Init(){ return 1; }
void orderCoins(){
    cout<<"orderCoins: "<<endl;
    for(int i=0;i<6;++i)cin>>coins[i],pos[coins[i]]=i;
}
void answer(int *a){
    cout<<"answer: ";
    for(int i=0;i<6;++i)cout<<a[i]<<" "; cout<<endl;
    cout<<"Query "<<qtime<<" times"<<endl;
}
int getHeaviest(int i,int j,int k){
    ++qtime;
    cout<<"getHeaviest "<<i<<" "<<j<<" "<<k<<endl;
    if(pos[i]>pos[j] && pos[i]>pos[k])return i;
    if(pos[j]>pos[i] && pos[j]>pos[k])return j;
    if(pos[k]>pos[i] && pos[k]>pos[j])return k;
}
int getLightest(int i,int j,int k){
    ++qtime;
    cout<<"getLightest "<<i<<" "<<j<<" "<<k<<endl;
    if(pos[i]<pos[j] && pos[i]<pos[k])return i;
    if(pos[j]<pos[i] && pos[j]<pos[k])return j;
    if(pos[k]<pos[i] && pos[k]<pos[j])return k;
}
int getMedian(int i,int j,int k){
    ++qtime;
    cout<<"getMedian "<<i<<" "<<j<<" "<<k<<endl;
    if((pos[i]>pos[j])^(pos[i]>pos[k]))return i;
    if((pos[j]>pos[i])^(pos[j]>pos[k]))return j;
    if((pos[k]>pos[i])^(pos[k]>pos[j]))return k;
}
int getNextLightest(int i,int j,int k,int l){
    ++qtime;
    cout<<"getNextLightest "<<i<<" "<<j<<" "<<k<<" "<<l<<endl;
    pair<int,int> pp[4]={{pos[i],i},{pos[j],j},{pos[k],k},{pos[l],l}};
    sort(pp,pp+4);
    if(pp[3].second==l)return pp[0].second;
    for(int i=0;i<3;++i)if(pp[i].second==l)return pp[i+1].second;
}
#pragma GCC diagnostic pop
#endif

struct operation{
    int type,arg1,arg2,arg3,arg4;
};
vector<operation> ops;

int go(vector<vector<int>> &now,bool okQ=0){
    if(now.size()<=1u)return 1;
    auto pnow=[&](){
        cout<<"now: "<<endl;
        for(auto &v:now){
            for(int i:v)cout<<i<<" ";
            cout<<endl;
        }
    };
    // pnow();
    // cout<<"okQ: "<<okQ<<endl;
    int pos[8];
    
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wreturn-type"
    auto _sim_getHeaviest=[&](const int i,const int j,const int k){
        if(pos[i]>pos[j] && pos[i]>pos[k])return i;
        if(pos[j]>pos[i] && pos[j]>pos[k])return j;
        if(pos[k]>pos[i] && pos[k]>pos[j])return k;
    };
    auto _sim_getLightest=[&](const int i,const int j,const int k){
        if(pos[i]<pos[j] && pos[i]<pos[k])return i;
        if(pos[j]<pos[i] && pos[j]<pos[k])return j;
        if(pos[k]<pos[i] && pos[k]<pos[j])return k;
    };
    auto _sim_getMedian=[&](const int i,const int j,const int k){
        if((pos[i]>pos[j])^(pos[i]>pos[k]))return i;
        if((pos[j]>pos[i])^(pos[j]>pos[k]))return j;
        if((pos[k]>pos[i])^(pos[k]>pos[j]))return k;
    };
    auto _sim_getNextLightest=[&](const int i,const int j,const int k,const int l){
        pair<int,int> pp[4]={{pos[i],i},{pos[j],j},{pos[k],k},{pos[l],l}};
        sort(pp,pp+4);
        if(pp[3].second==l)return pp[0].second;
        for(int i=0;i<3;++i)if(pp[i].second==l)return pp[i+1].second;
    };
#pragma GCC diagnostic pop

    for(int i=1;i<=4;++i){
        for(int j=i+1;j<=5;++j){
            for(int k=j+1;k<=6;++k){
                int r1=0,r2=0,r3=0,lim=(now.size()+2)/3;
                for(auto &v:now){
                    for(int i=0;i<6;++i)pos[v[i]]=i;
                    int r=_sim_getHeaviest(i,j,k);
                    if(r==i)++r1;
                    if(r==j)++r2;
                    if(r==k)++r3;
                }
                // cout<<"rrrl: "<<r1<<" "<<r2<<" "<<r3<<" "<<lim<<endl;
                if(r1<=lim && r2<=lim && r3<=lim){
                    vector<vector<int>> v1,v2,v3;
                    for(auto &v:now){
                        for(int i=0;i<6;++i)pos[v[i]]=i;
                        int r=_sim_getHeaviest(i,j,k);
                        if(r==i)v1.push_back(v);
                        if(r==j)v2.push_back(v);
                        if(r==k)v3.push_back(v);
                    }
                    int ok=go(v1)+go(v2)+go(v3);
                    if(ok>=3){
                        if(!okQ)return 1;
                        vector<vector<int>> tmp;
                        int r=getHeaviest(i,j,k);
                        for(auto &v:now){
                            for(int i=0;i<6;++i)pos[v[i]]=i;
                            if(_sim_getHeaviest(i,j,k)==r)tmp.push_back(v);
                        }
                        now.swap(tmp);
                        assert(go(now,1)==1);
                        return 1;
                    }
                }

                r1=r2=r3=0;
                for(auto &v:now){
                    for(int i=0;i<6;++i)pos[v[i]]=i;
                    int r=_sim_getLightest(i,j,k);
                    if(r==i)++r1;
                    if(r==j)++r2;
                    if(r==k)++r3;
                }
                // cout<<"rrrl: "<<r1<<" "<<r2<<" "<<r3<<" "<<lim<<endl;
                if(r1<=lim && r2<=lim && r3<=lim){
                    vector<vector<int>> v1,v2,v3;
                    for(auto &v:now){
                        for(int i=0;i<6;++i)pos[v[i]]=i;
                        int r=_sim_getLightest(i,j,k);
                        if(r==i)v1.push_back(v);
                        if(r==j)v2.push_back(v);
                        if(r==k)v3.push_back(v);
                    }
                    int ok=go(v1)+go(v2)+go(v3);
                    if(ok>=3){
                        if(!okQ)return 1;
                        vector<vector<int>> tmp;
                        int r=getLightest(i,j,k);
                        for(auto &v:now){
                            for(int i=0;i<6;++i)pos[v[i]]=i;
                            if(_sim_getLightest(i,j,k)==r)tmp.push_back(v);
                        }
                        now.swap(tmp);
                        assert(go(now,1)==1);
                        return 1;
                    }
                }

                r1=r2=r3=0;
                for(auto &v:now){
                    for(int i=0;i<6;++i)pos[v[i]]=i;
                    int r=_sim_getMedian(i,j,k);
                    if(r==i)++r1;
                    if(r==j)++r2;
                    if(r==k)++r3;
                }
                // cout<<"rrrl: "<<r1<<" "<<r2<<" "<<r3<<" "<<lim<<endl;
                if(r1<=lim && r2<=lim && r3<=lim){
                    vector<vector<int>> v1,v2,v3;
                    for(auto &v:now){
                        for(int i=0;i<6;++i)pos[v[i]]=i;
                        int r=_sim_getMedian(i,j,k);
                        if(r==i)v1.push_back(v);
                        if(r==j)v2.push_back(v);
                        if(r==k)v3.push_back(v);
                    }
                    int ok=go(v1)+go(v2)+go(v3);
                    if(ok>=3){
                        if(!okQ)return 1;
                        vector<vector<int>> tmp;
                        int r=getMedian(i,j,k);
                        for(auto &v:now){
                            for(int i=0;i<6;++i)pos[v[i]]=i;
                            if(_sim_getMedian(i,j,k)==r)tmp.push_back(v);
                        }
                        now.swap(tmp);
                        assert(go(now,1)==1);
                        return 1;
                    }
                }

                for(int l=1;l<=6;++l){
                    if(l==i || l==j || l==k)continue;
                    r1=r2=r3=0;
                    for(auto &v:now){
                        for(int i=0;i<6;++i)pos[v[i]]=i;
                        int r=_sim_getNextLightest(i,j,k,l);
                        if(r==i)++r1;
                        if(r==j)++r2;
                        if(r==k)++r3;
                    }
                // cout<<"rrrl: "<<r1<<" "<<r2<<" "<<r3<<" "<<lim<<endl;
                    if(r1<=lim && r2<=lim && r3<=lim){
                        vector<vector<int>> v1,v2,v3;
                        for(auto &v:now){
                            for(int i=0;i<6;++i)pos[v[i]]=i;
                            int r=_sim_getNextLightest(i,j,k,l);
                            if(r==i)v1.push_back(v);
                            if(r==j)v2.push_back(v);
                            if(r==k)v3.push_back(v);
                        }
                        int ok=go(v1)+go(v2)+go(v3);
                        if(ok>=3){
                            if(!okQ)return 1;
                            vector<vector<int>> tmp;
                            int r=getNextLightest(i,j,k,l);
                            for(auto &v:now){
                                for(int i=0;i<6;++i)pos[v[i]]=i;
                                if(_sim_getNextLightest(i,j,k,l)==r)tmp.push_back(v);
                            }
                            now.swap(tmp);
                            assert(go(now,1)==1);
                            return 1;
                        }
                    }
                }
            }
        }
    }
    return 0;
}



#ifdef WEAK
int main(){
    int t=Init(); while(t--){
        orderCoins();
        int a[6]={1,2,3,4,5,6};
        vector<vector<int>> now;
        vector<int> tmp(a,a+6);
        do{
            now.push_back(tmp);
        }while(next_permutation(tmp.begin(),tmp.end()));
        go(now,1);
        for(int i=0;i<6;++i)a[i]=now[0][i];
        answer(a);
    }
}
#else
void init(int T){}
void orderCoins(){
    int a[6]={1,2,3,4,5,6};
    vector<vector<int>> now;
    vector<int> tmp(a,a+6);
    do{
        now.push_back(tmp);
    }while(next_permutation(tmp.begin(),tmp.end()));
    go(now,1);
    for(int i=0;i<6;++i)a[i]=now[0][i];
    answer(a);
}
#endif

Compilation message (stderr)

In file included from grader.c:2:0:
graderlib.c: In function 'void answer(int*)':
graderlib.c:53:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (_ghksjhdfkae19ga_ > 1) 
     ^~
graderlib.c:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  for (i = 0; i < 6; i++) {
  ^~~
scales.cpp: In lambda function:
scales.cpp:92:17: warning: declaration of 'int i' shadows a parameter [-Wshadow]
         for(int i=0;i<3;++i)if(pp[i].second==l)return pp[i+1].second;
                 ^
scales.cpp:88:45: note: shadowed declaration is here
     auto _sim_getNextLightest=[&](const int i,const int j,const int k,const int l){
                                             ^
scales.cpp: In function 'int go(std::vector<std::vector<int> >&, bool)':
scales.cpp:99:54: warning: conversion to 'int' from 'std::vector<std::vector<int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
                 int r1=0,r2=0,r3=0,lim=(now.size()+2)/3;
                                        ~~~~~~~~~~~~~~^~
scales.cpp:101:29: warning: declaration of 'i' shadows a previous local [-Wshadow]
                     for(int i=0;i<6;++i)pos[v[i]]=i;
                             ^
scales.cpp:96:13: note: shadowed declaration is here
     for(int i=1;i<=4;++i){
             ^
scales.cpp:111:33: warning: declaration of 'i' shadows a previous local [-Wshadow]
                         for(int i=0;i<6;++i)pos[v[i]]=i;
                                 ^
scales.cpp:96:13: note: shadowed declaration is here
     for(int i=1;i<=4;++i){
             ^
scales.cpp:123:37: warning: declaration of 'i' shadows a previous local [-Wshadow]
                             for(int i=0;i<6;++i)pos[v[i]]=i;
                                     ^
scales.cpp:96:13: note: shadowed declaration is here
     for(int i=1;i<=4;++i){
             ^
scales.cpp:134:29: warning: declaration of 'i' shadows a previous local [-Wshadow]
                     for(int i=0;i<6;++i)pos[v[i]]=i;
                             ^
scales.cpp:96:13: note: shadowed declaration is here
     for(int i=1;i<=4;++i){
             ^
scales.cpp:144:33: warning: declaration of 'i' shadows a previous local [-Wshadow]
                         for(int i=0;i<6;++i)pos[v[i]]=i;
                                 ^
scales.cpp:96:13: note: shadowed declaration is here
     for(int i=1;i<=4;++i){
             ^
scales.cpp:156:37: warning: declaration of 'i' shadows a previous local [-Wshadow]
                             for(int i=0;i<6;++i)pos[v[i]]=i;
                                     ^
scales.cpp:96:13: note: shadowed declaration is here
     for(int i=1;i<=4;++i){
             ^
scales.cpp:167:29: warning: declaration of 'i' shadows a previous local [-Wshadow]
                     for(int i=0;i<6;++i)pos[v[i]]=i;
                             ^
scales.cpp:96:13: note: shadowed declaration is here
     for(int i=1;i<=4;++i){
             ^
scales.cpp:177:33: warning: declaration of 'i' shadows a previous local [-Wshadow]
                         for(int i=0;i<6;++i)pos[v[i]]=i;
                                 ^
scales.cpp:96:13: note: shadowed declaration is here
     for(int i=1;i<=4;++i){
             ^
scales.cpp:189:37: warning: declaration of 'i' shadows a previous local [-Wshadow]
                             for(int i=0;i<6;++i)pos[v[i]]=i;
                                     ^
scales.cpp:96:13: note: shadowed declaration is here
     for(int i=1;i<=4;++i){
             ^
scales.cpp:202:33: warning: declaration of 'i' shadows a previous local [-Wshadow]
                         for(int i=0;i<6;++i)pos[v[i]]=i;
                                 ^
scales.cpp:96:13: note: shadowed declaration is here
     for(int i=1;i<=4;++i){
             ^
scales.cpp:212:37: warning: declaration of 'i' shadows a previous local [-Wshadow]
                             for(int i=0;i<6;++i)pos[v[i]]=i;
                                     ^
scales.cpp:96:13: note: shadowed declaration is here
     for(int i=1;i<=4;++i){
             ^
scales.cpp:224:41: warning: declaration of 'i' shadows a previous local [-Wshadow]
                                 for(int i=0;i<6;++i)pos[v[i]]=i;
                                         ^
scales.cpp:96:13: note: shadowed declaration is here
     for(int i=1;i<=4;++i){
             ^
scales.cpp:60:10: warning: variable 'pnow' set but not used [-Wunused-but-set-variable]
     auto pnow=[&](){
          ^~~~
scales.cpp: In function 'void init(int)':
scales.cpp:257:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T){}
               ^

• Subtask 1: 100 / 100