Submission #984617

#	Time	Username	Problem	Language	Result	Execution time	Memory
984617		jay_jayjay	Scales (IOI15_scales)	C++14	100 / 100	14 ms	604 KiB

scales

// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <bits/stdc++.h>
using namespace std;

#include <tr2/dynamic_bitset>
using namespace tr2;
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll

#include <assert.h>
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#endif
#define all(x) (x).begin(), (x).end()
struct cintype { template<typename T> operator T() { T x; cin>>x; return x; } };
// 1}}}
#include "scales.h"

struct query {
        char t, a, b, c, d;

        query(){}
        query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}

        int ex() {
                int C=0;
                switch(t) {
                        case 1: C=getHeaviest(a+1,b+1,c+1); break;
                        case 2: C=getLightest(a+1,b+1,c+1); break;
                        case 3: C=getMedian(a+1,b+1,c+1); break;
                        case 4: C=getNextLightest(a+1,b+1,c+1,d+1); break;
                }
                C--;
                //printf("ex %d | %d %d %d | %d : %d\n",t,a,b,c,d,C);
                return C==a?0:C==b?1:C==c?2:-1;
        }
        int sim(array<char,6> p) {
                array<array<char,2>,3> q{ array<char,2>{p[a],a},array<char,2>{p[b],b},array<char,2>{p[c],c} };
                sort(all(q));
                auto [x,y,z] = q;
                int C=0;
                switch(t) {
                        case 1: C=z[1]; break;
                        case 2: C=x[1]; break;
                        case 3: C=y[1]; break;
                        case 4: C=p[d]<x[0]?x[1]:p[d]<y[0]?y[1]:p[d]<z[0]?z[1]:x[1]; break;
                }
                return C==a?0:C==b?1:C==c?2:-1;
        }
        bool operator < (const query& o) const { return make_tuple(t,a,b,c,d)<make_tuple(o.t,o.a,o.b,o.c,o.d); }
};

query Q[5000];

int work(int p, int T, vector<array<char,6>> z) {
        if(z.size()<=1)return 0;
        if(T==6)return 1;
        //printf("%d %d %d\n",p,T,z.size());
        //if(z.size()<10) for(auto v:z){for(auto x:v)printf("%d",x);printf("\n");}
        if(T==0) {
                for(auto q : {query{1,1,2,3,4},query{2,1,2,3,4},query{3,1,2,3,4},query{4,1,2,3,4}}) {
                        array<vector<array<char,6>>,3> np;
                        for(auto&x:z) np[q.sim(x)].push_back(x);
                        int mx = max({np[0].size(),np[1].size(),np[2].size()});
                        if(mx>240)continue;
                        if(work(3*p+1,T+1, np[0])) continue;
                        if(work(3*p+2,T+1, np[1])) continue;
                        if(work(3*p+3,T+1, np[2])) continue;
                        Q[p]=q;
                        return 0;
                }
                return 1;
        }
        for(int t=1;t<5;t++) {
                for(int d=0;d<(t==4?6:1);d++) {
                        for(int a=0;a<6;a++)
                                for(int b=a+1;b<6;b++)
                                        for(int c=b+1;c<6;c++) {
                                                if(t==4 && (a==d||b==d||c==d)) continue;
                                                query q{t,a,b,c,d};
                                                array<vector<array<char,6>>,3> np;
                                                for(auto&x:z) np[q.sim(x)].push_back(x);
                                                int mx = max({np[0].size(),np[1].size(),np[2].size()});
                                                if(T==1&&mx>80)continue;
                                                if(T==2&&mx>27)continue;
                                                if(T==3&&mx>9)continue;
                                                if(T==4&&mx>3)continue;
                                                if(T==5&&mx>1)continue;

                                                if(work(3*p+1,T+1, np[0])) continue;
                                                if(work(3*p+2,T+1, np[1])) continue;
                                                if(work(3*p+3,T+1, np[2])) continue;
                                                Q[p]=q;
                                                return 0;
                                        }
                }
        }
        return 1;
}

void init(int T) {
        if(query(1,1,2,3,4).sim({1,2,3,4,5,6}) != 2)assert(0);
        if(query(2,1,2,3,4).sim({1,2,3,4,5,6}) != 0)assert(0);
        if(query(3,1,2,3,4).sim({1,2,3,4,5,6}) != 1)assert(0);
        if(query(3,1,3,4,2).sim({1,2,3,4,5,6}) != 1)assert(0);
        vector<array<char,6>> v;
        array<char,6> a{1,2,3,4,5,6};
        do { v.push_back(a); } while(next_permutation(all(a)));

        int st = work(0, 0, v);
        //printf("%d\n",st);
}

void orderCoins() {
        vector<array<char,6>> v;
        array<char,6> a{1,2,3,4,5,6};
        do { v.push_back(a); } while(next_permutation(all(a)));


        int i=0;
        while(v.size()>1) {
                //printf("%d %d\n",i, v.size());
                query q = Q[i];
                int s;
                i = i*3 + (s=q.ex())+1;
                decltype(v) nv;
                for(auto p:v)if(q.sim(p)==s)nv.push_back(p);
                v=nv;
        }
        //printf("%d %d\n",i, v.size());

        auto p=v[0];
        int W[6];
        for(int i=0;i<6;i++)W[+p[i]-1] = i+1;
        answer(W);
}

Compilation message (stderr)

scales.cpp: In constructor 'query::query(int, int, int, int, int)':
scales.cpp:30:47: warning: declaration of 'd' shadows a member of 'query' [-Wshadow]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                                           ~~~~^
scales.cpp:27:26: note: shadowed declaration is here
   27 |         char t, a, b, c, d;
      |                          ^
scales.cpp:30:40: warning: declaration of 'c' shadows a member of 'query' [-Wshadow]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                                    ~~~~^
scales.cpp:27:23: note: shadowed declaration is here
   27 |         char t, a, b, c, d;
      |                       ^
scales.cpp:30:33: warning: declaration of 'b' shadows a member of 'query' [-Wshadow]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                             ~~~~^
scales.cpp:27:20: note: shadowed declaration is here
   27 |         char t, a, b, c, d;
      |                    ^
scales.cpp:30:26: warning: declaration of 'a' shadows a member of 'query' [-Wshadow]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                      ~~~~^
scales.cpp:27:17: note: shadowed declaration is here
   27 |         char t, a, b, c, d;
      |                 ^
scales.cpp:30:19: warning: declaration of 't' shadows a member of 'query' [-Wshadow]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |               ~~~~^
scales.cpp:27:14: note: shadowed declaration is here
   27 |         char t, a, b, c, d;
      |              ^
scales.cpp:30:54: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                                                      ^
scales.cpp:30:59: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                                                           ^
scales.cpp:30:64: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                                                                ^
scales.cpp:30:69: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                                                                     ^
scales.cpp:30:74: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                                                                          ^
scales.cpp: In constructor 'query::query(int, int, int, int, int)':
scales.cpp:30:47: warning: declaration of 'd' shadows a member of 'query' [-Wshadow]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                                           ~~~~^
scales.cpp:27:26: note: shadowed declaration is here
   27 |         char t, a, b, c, d;
      |                          ^
scales.cpp:30:40: warning: declaration of 'c' shadows a member of 'query' [-Wshadow]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                                    ~~~~^
scales.cpp:27:23: note: shadowed declaration is here
   27 |         char t, a, b, c, d;
      |                       ^
scales.cpp:30:33: warning: declaration of 'b' shadows a member of 'query' [-Wshadow]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                             ~~~~^
scales.cpp:27:20: note: shadowed declaration is here
   27 |         char t, a, b, c, d;
      |                    ^
scales.cpp:30:26: warning: declaration of 'a' shadows a member of 'query' [-Wshadow]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                      ~~~~^
scales.cpp:27:17: note: shadowed declaration is here
   27 |         char t, a, b, c, d;
      |                 ^
scales.cpp:30:19: warning: declaration of 't' shadows a member of 'query' [-Wshadow]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |               ~~~~^
scales.cpp:27:14: note: shadowed declaration is here
   27 |         char t, a, b, c, d;
      |              ^
scales.cpp: In constructor 'query::query(int, int, int, int, int)':
scales.cpp:30:47: warning: declaration of 'd' shadows a member of 'query' [-Wshadow]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                                           ~~~~^
scales.cpp:27:26: note: shadowed declaration is here
   27 |         char t, a, b, c, d;
      |                          ^
scales.cpp:30:40: warning: declaration of 'c' shadows a member of 'query' [-Wshadow]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                                    ~~~~^
scales.cpp:27:23: note: shadowed declaration is here
   27 |         char t, a, b, c, d;
      |                       ^
scales.cpp:30:33: warning: declaration of 'b' shadows a member of 'query' [-Wshadow]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                             ~~~~^
scales.cpp:27:20: note: shadowed declaration is here
   27 |         char t, a, b, c, d;
      |                    ^
scales.cpp:30:26: warning: declaration of 'a' shadows a member of 'query' [-Wshadow]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |                      ~~~~^
scales.cpp:27:17: note: shadowed declaration is here
   27 |         char t, a, b, c, d;
      |                 ^
scales.cpp:30:19: warning: declaration of 't' shadows a member of 'query' [-Wshadow]
   30 |         query(int t, int a, int b, int c, int d) : t(t),a(a),b(b),c(c),d(d) {}
      |               ~~~~^
scales.cpp:27:14: note: shadowed declaration is here
   27 |         char t, a, b, c, d;
      |              ^
scales.cpp: In member function 'int query::sim(std::array<char, 6>)':
scales.cpp:47:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |                 auto [x,y,z] = q;
      |                      ^
scales.cpp: In function 'int work(int, int, std::vector<std::array<char, 6> >)':
scales.cpp:71:37: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
   71 |                         int mx = max({np[0].size(),np[1].size(),np[2].size()});
      |                                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:90:61: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
   90 |                                                 int mx = max({np[0].size(),np[1].size(),np[2].size()});
      |                                                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:117:13: warning: unused variable 'st' [-Wunused-variable]
  117 |         int st = work(0, 0, v);
      |             ^~
scales.cpp:108:15: warning: unused parameter 'T' [-Wunused-parameter]
  108 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:141:17: warning: declaration of 'i' shadows a previous local [-Wshadow]
  141 |         for(int i=0;i<6;i++)W[+p[i]-1] = i+1;
      |                 ^
scales.cpp:127:13: note: shadowed declaration is here
  127 |         int i=0;
      |             ^

• Subtask 1: 100 / 100