Submission #55476

#	Time	Username	Problem	Language	Result	Execution time	Memory
55476		alenam0161	Scales (IOI15_scales)	C++17	0 / 100	6 ms	1564 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > comb;
vector<vector<int> > Q;
struct node{
    vector<vector<int> > q_and_ans;
    vector<int> good;
    int Ok=true;
    int nxt;
    int sz[4];
    void init(){
        q_and_ans.resize(0);
        good.resize(0);
    }
};
vector<node> cmp;
vector<int> ps;
int get_ans(vector<int> rng,vector<int> q){
    ps.resize(6,0);
    for(int i=0;i<6;++i)ps[rng[i]]=i;
    int a1=ps[q[1]];
    int a2=ps[q[2]];
    int a3=ps[q[3]];
    int a4=ps[q[4]];
    vector<pair<int,int> > qw;
    qw.push_back(make_pair(ps[q[1]],q[1]));
    qw.push_back(make_pair(ps[q[2]],q[2]));
    qw.push_back(make_pair(ps[q[3]],q[3]));
    sort(qw.begin(),qw.end());
    if(q[0]==0)return qw[0].second;
    if(q[0]==1)return qw[1].second;
    if(q[0]==2)return qw[2].second;
    if(q[0]==3){
        if(ps[q[4]]<qw[2].first&&ps[q[4]]>qw[1].first)return qw[2].second;
        if(ps[q[4]]<qw[1].first&&ps[q[4]]>qw[0].first)return qw[1].second;
        return qw[0].second;
    }
}
int y=0;
void rec(int ps,int lv){
    if(lv==6){
        int hw=0;
        cmp[ps].Ok=false;
        for(int i=0;i<comb.size();++i){
            bool ok=true;
            for(int d=0;d<cmp[ps].q_and_ans.size();++d){
                vector<int> qw=cmp[ps].q_and_ans[d];qw.pop_back();
                if(cmp[ps].q_and_ans[d][5]!=get_ans(comb[i],qw)){
                    ok=false;break;
                }
            }
            if(ok){
                cmp[ps].good=comb[i];hw++;
            }
        }
        if(hw!=1)cmp[ps].Ok=false;
        return;
    }
    else{
        for(int i=0;i<Q.size();++i){
            vector<int> w=Q[i];w.push_back(0);
            cmp.push_back(node());
            int s1=cmp.size()-1;
            cmp[s1].q_and_ans=cmp[ps].q_and_ans;
            w[5]=w[1];
            cmp[s1].q_and_ans.push_back(w);
            rec(s1,lv+1);
            bool o1=cmp[s1].Ok;
            cmp.push_back(node());
            int s2=cmp.size()-1;
            cmp[s2].q_and_ans=cmp[ps].q_and_ans;
            w[5]=w[2];
            cmp[s2].q_and_ans.push_back(w);
            rec(s2,lv+1);
            bool o2=cmp[s2].Ok;
            cmp.push_back(node());
            int s3=cmp.size()-1;
            cmp[s3].q_and_ans=cmp[ps].q_and_ans;
            w[5]=w[3];
            cmp[s3].q_and_ans.push_back(w);
            rec(s3,lv+1);
            bool o3=cmp[s3].Ok;
            if(o1==true&&o2==true&&o3==true){
                cmp[ps].Ok=true;
                cmp[ps].nxt=i;
                cmp[ps].sz[0]=s1;
                cmp[ps].sz[1]=s2;
                cmp[ps].sz[2]=s3;
                goto en;
            }
        }
    }
    en:
        y++;
}
void init(int T) {
    vector<int> fi;
    for(int i=0;i<6;++i)fi.push_back(i+1);
    do{
        comb.push_back(fi);
    }while(next_permutation(fi.begin(),fi.end()));
    for(int i=1;i<=6;++i)
        for(int j=1;j<=6;++j){
        if(i==j)continue;
            for(int k=1;k<=6;++k){
                if(k==i||k==j)continue;
                vector<int> kd(5);
                kd[0]=0;
                kd[1]=i;
                kd[2]=j;
                kd[3]=k;
                Q.push_back(kd);
                kd[0]=1;
                Q.push_back(kd);
                kd[0]=2;
                Q.push_back(kd);
                kd[0]=3;
                for(int e=1;e<=6;++e){
                    if(i==e||j==e||k==e)continue;
                    kd[4]=e;
                    Q.push_back(kd);
                }
            }
        }
    cout<<comb.size()<<" "<<Q.size()<<endl;
    cmp.push_back(node());
    rec(0,0);
}

void orderCoins() {
    int cp=0;
    for(int i=0;i<6;++i){
        int a0=Q[cmp[cp].nxt][0];
        int a1=Q[cmp[cp].nxt][1];
        int a2=Q[cmp[cp].nxt][2];
        int a3=Q[cmp[cp].nxt][3];
        int a4=Q[cmp[cp].nxt][4];
        int f;
        if(a0==0){
            f=getLightest(a1,a2,a3);
        }
        if(a0==1){
            f=getMedian(a1,a2,a3);
        }
        if(a0==2){
            f=getHeaviest(a1,a2,a3);
        }
        if(a0==3){
            f=getNextLightest(a1,a2,a3,a4);
        }
        if(f==a1)cp=cmp[cp].sz[0];
        if(f==a2)cp=cmp[cp].sz[1];
        if(f==a3)cp=cmp[cp].sz[2];
    }
    int W[6];
    for(int i=0;i<6;++i){
        W[i]=cmp[cp].good[i];
    }
    answer(W);
}

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 function 'int get_ans(std::vector<int>, std::vector<int>)':
scales.cpp:22:9: warning: unused variable 'a1' [-Wunused-variable]
     int a1=ps[q[1]];
         ^~
scales.cpp:23:9: warning: unused variable 'a2' [-Wunused-variable]
     int a2=ps[q[2]];
         ^~
scales.cpp:24:9: warning: unused variable 'a3' [-Wunused-variable]
     int a3=ps[q[3]];
         ^~
scales.cpp:25:9: warning: unused variable 'a4' [-Wunused-variable]
     int a4=ps[q[4]];
         ^~
scales.cpp: In function 'void rec(int, int)':
scales.cpp:41:23: warning: declaration of 'ps' shadows a global declaration [-Wshadow]
 void rec(int ps,int lv){
                       ^
scales.cpp:18:13: note: shadowed declaration is here
 vector<int> ps;
             ^~
scales.cpp:45:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<comb.size();++i){
                     ~^~~~~~~~~~~~
scales.cpp:47:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int d=0;d<cmp[ps].q_and_ans.size();++d){
                         ~^~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:61:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<Q.size();++i){
                     ~^~~~~~~~~
scales.cpp:64:30: warning: conversion to 'int' from 'std::vector<node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
             int s1=cmp.size()-1;
                    ~~~~~~~~~~^~
scales.cpp:71:30: warning: conversion to 'int' from 'std::vector<node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
             int s2=cmp.size()-1;
                    ~~~~~~~~~~^~
scales.cpp:78:30: warning: conversion to 'int' from 'std::vector<node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
             int s3=cmp.size()-1;
                    ~~~~~~~~~~^~
scales.cpp: In function 'void init(int)':
scales.cpp:97:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^
scales.cpp: In function 'int get_ans(std::vector<int>, std::vector<int>)':
scales.cpp:39:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
scales.cpp: In function 'void orderCoins()':
scales.cpp:154:9: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if(f==a3)cp=cmp[cp].sz[2];
         ^~

• Subtask 1: 0 / 100