Submission #707989

#	Time	Username	Problem	Language	Result	Execution time	Memory
707989		abcvuitunggio	Scales (IOI15_scales)	C++17	100 / 100	271 ms	9372 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
#define BS bitset <720>
using namespace std;
struct question{
    int a[4];
    int type;
};
unordered_map <BS, int> mp[7];
BS p[120][3];
vector <vector <int>> v;
vector <question> vq;
int pw[7];
int ask(int i){
    int res=0;
    if (!vq[i].type)
        res=getLightest(vq[i].a[0],vq[i].a[1],vq[i].a[2]);
    if (vq[i].type==1)
        res=getMedian(vq[i].a[0],vq[i].a[1],vq[i].a[2]);
    if (vq[i].type==2)
        res=getHeaviest(vq[i].a[0],vq[i].a[1],vq[i].a[2]);
    if (vq[i].type==3)
        res=getNextLightest(vq[i].a[0],vq[i].a[1],vq[i].a[2],vq[i].a[3]);
    return (res==vq[i].a[0]?0:(res==vq[i].a[1]?1:2));
}
int f(BS b, int id){
    if (b.count()>pw[id])
        return -1;
    if (!id)
        return -2;
    if (b.count()<2)
        return -2;
    if (mp[id].count(b))
        return mp[id][b];
    for (int i=0;i<vq.size();i++){
        bool ch=true;
        for (int j=0;j<3;j++)
            if (f(b&p[i][j],id-1)==-1){
                ch=false;
                break;
            }
        if (ch)
            return mp[id][b]=i;
    }
    return mp[id][b]=-1;
}
bool isLightest(vector <int> a, int i, int j, int k){
    return (a[i]<min(a[j],a[k]));
}
bool isMedian(vector <int> a, int i, int j, int k){
    return (a[j]-a[i])*(a[j]-a[k])<0;
}
bool isHeaviest(vector <int> a, int i, int j, int k){
    return (a[i]>max(a[j],a[k]));
}
bool isNextLightest(vector <int> a, int i, int j, int k, int l){
    if (max(a[i],max(a[j],a[k]))<a[l])
        return isLightest(a,i,j,k);
    if (a[i]<a[l])
        return false;
    return (!((a[j]>a[l]&&a[j]<a[i])||(a[k]>a[l]&&a[k]<a[i])));
}
void init(int T){
    v.clear();
    vq.clear();
    pw[0]=1;
    for (int i=1;i<=6;i++)
        pw[i]=pw[i-1]*3;
    vector <int> ve;
    for (int i=1;i<=6;i++)
        ve.push_back(i);
    do{
        v.push_back(ve);
    }while (next_permutation(ve.begin(),ve.end()));
    int id=0;
    for (int i=1;i<=6;i++)
        for (int j=i+1;j<=6;j++)
            for (int k=j+1;k<=6;k++){
                for (int l=0;l<3;l++)
                    vq.push_back({i,j,k,0,l});
                for (int l=1;l<=6;l++)
                    if (l!=i&&l!=j&&l!=k)
                        vq.push_back({i,j,k,l,3});
            }
    for (int i=0;i<vq.size();i++)
        for (int j=0;j<v.size();j++){
            for (int k=0;k<3;k++){
                if (!vq[i].type&&isLightest(v[j],vq[i].a[k]-1,vq[i].a[(k+1)%3]-1,vq[i].a[(k+2)%3]-1))
                    p[i][k][j]=1;
                if (vq[i].type==1&&isMedian(v[j],vq[i].a[(k+1)%3]-1,vq[i].a[k]-1,vq[i].a[(k+2)%3]-1))
                    p[i][k][j]=1;
                if (vq[i].type==2&&isHeaviest(v[j],vq[i].a[k]-1,vq[i].a[(k+1)%3]-1,vq[i].a[(k+2)%3]-1))
                    p[i][k][j]=1;
                if (vq[i].type==3&&isNextLightest(v[j],vq[i].a[k]-1,vq[i].a[(k+1)%3]-1,vq[i].a[(k+2)%3]-1,vq[i].a[3]-1))
                    p[i][k][j]=1;
            }
        }
}
void orderCoins(){
    int W[] = {1, 2, 3, 4, 5, 6};
    BS b;
    for (int i=0;i<720;i++)
        b[i]=1;
    int tmp=f(b,6);
    for (int i=6;i>=1;i--){
        int x=mp[i][b];
        int y=ask(x);
        b&=p[x][y];
        if (b.count()==1)
            break;
    }
    int pos=0;
    for (int i=0;i<720;i++)
        if (b[i]){
            pos=i;
            break;
        }
    for (int i=0;i<6;i++)
        W[v[pos][i]-1]=i+1;
    answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'int f(std::bitset<720>, int)':
scales.cpp:27:18: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |     if (b.count()>pw[id])
      |         ~~~~~~~~~^~~~~~~
scales.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<question>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i=0;i<vq.size();i++){
      |                  ~^~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:85:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<question>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i=0;i<vq.size();i++)
      |                  ~^~~~~~~~~~
scales.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for (int j=0;j<v.size();j++){
      |                      ~^~~~~~~~~
scales.cpp:75:9: warning: unused variable 'id' [-Wunused-variable]
   75 |     int id=0;
      |         ^~
scales.cpp:63:15: warning: unused parameter 'T' [-Wunused-parameter]
   63 | void init(int T){
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:104:9: warning: unused variable 'tmp' [-Wunused-variable]
  104 |     int tmp=f(b,6);
      |         ^~~

• Subtask 1: 100 / 100