제출 #707984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
707984		abcvuitunggio	Scales (IOI15_scales)	C++17	0 / 100	334 ms	18772 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
#define BS bitset <720>
//#define NAM
using namespace std;
#ifdef NAM
vector <int> order={1,2,3,4,5,6};
int w[7],cnt;
int getLightest(int i, int j, int k){
    cnt++;
    if (w[i]<w[j]&&w[i]<w[k])
        return i;
    return (w[j]<w[k]?j:k);
}
int getHeaviest(int i, int j, int k){
    cnt++;
    if (w[i]>w[j]&&w[i]>w[k])
        return i;
    return (w[j]>w[k]?j:k);
}
int getMedian(int i, int j, int k){
    cnt--;
    return i+j+k-getLightest(i,j,k)-getHeaviest(i,j,k);
}
int getNextLightest(int i, int j, int k, int l){
    if (w[l]>max(w[i],max(w[j],w[k])))
        return getLightest(i,j,k);
    cnt++;
    int mn=100,res=-1;
    if (w[i]>w[l]&&mn>w[i]){
        mn=w[i];
        res=i;
    }
    if (w[j]>w[l]&&mn>w[j]){
        mn=w[j];
        res=j;
    }
    if (w[k]>w[l]&&mn>w[k]){
        mn=w[k];
        res=k;
    }
    return res;
}
void answer(int W[]){
    for (int i=0;i<6;i++){
        cout << W[i] << ' ';
        assert(W[i]==order[i]);
    }
}
#endif
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;
}
void init(int T){
    v.clear();
    vq.clear();
    pw[0]=1;
    for (int i=1;i<=6;i++)
        pw[i]=pw[i-1]*3;
}
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 orderCoins(){
    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;
            }
        }
    int W[] = {1, 2, 3, 4, 5, 6};
    BS b;
    for (int i=0;i<720;i++)
        b[i]=1;
    for (int i=6;i>=1;i--){
        int x=f(b,i);
        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);
}
#ifdef NAM
void run(){
    init(1);
    cnt=0;
    for (int i=0;i<order.size();i++)
        w[order[i]]=i+1;
    orderCoins();
    cout << '\n' << cnt << '\n';
}
int main(){
    do{
        run();
    }while (next_permutation(order.begin(),order.end()));
}
#endif // NAM

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 0 / 100