Submission #713734

#	Time	Username	Problem	Language	Result	Execution time	Memory
713734		lam	Scales (IOI15_scales)	C++14	100 / 100	39 ms	544 KiB

scales

#include <bits/stdc++.h>
#include "scales.h"
using namespace std;
vector <vector <int>> asks, pos, perm;
int lt3[11];
int query(vector <int> v)
{
    if (v[0] == 0) return getLightest(v[1],v[2],v[3]);
    if (v[0] == -1) return getMedian(v[1],v[2],v[3]);
    if (v[0] == -2) return getHeaviest(v[1],v[2],v[3]);
    return getNextLightest(v[1],v[2],v[3],v[0]);
}

int query2(int id, vector <int> v)
{
    sort(v.begin()+1,v.end(),[&](int a, int b){
         return pos[id][a] < pos[id][b]; });
    if (v[0] < 1) return v[1-v[0]];
    for (int i=1; i<=3; i++) if (pos[id][v[i]] > pos[id][v[0]]) return v[i];
    return v[1];
}

struct Cmp {
    bool operator() (const bitset<720> &a, const bitset<720> &b) const {
        for (int i=0; i<720; i++) if (a[i] != b[i]) return a[i] < b[i];
        return false;
    }
};
map<bitset<720>,vector <int>,Cmp> mp[10];

bool check(bitset<720> bs, int level)
{
//    assert(level>=1);
//    if (level)
//    {
//        for (int i=0; i<720; i++) cerr<<bs[i]; cerr<<endl;
//    }
    if (bs.count()<=1) return 1;
    if (mp[level].count(bs)) return !mp[level][bs].empty();
    int num = 0;
    for (vector <int> v:asks)
    {
        vector <int> id(7);
        for (int i=1; i<=3; i++) id[v[i]] = i-1;
        vector<bitset<720>> nxt(3);
        for (int i=0; i<720; i++) if (bs[i]) nxt[id[query2(i,v)]][i] = 1;
        bool ccheck = 1;
        for (auto bs2:nxt)
            if (bs2.count() > lt3[level-1])
            {
                ccheck = 0;
                break;
            }
        if (!ccheck) continue;
        for (auto bs2:nxt)
            if (!check(bs2,level-1))
        {
            ccheck = 0;
            break;
        }
        if (ccheck)
        {
            mp[level][bs] = v;
//            assert(false);
            return 1;
        }
    }
    mp[level][bs] = {};
    return 0;
}

void init(int test)
{
    lt3[0] = 1;
    for (int i=1; i<=10; i++) lt3[i] = lt3[i-1] * 3;
    vector <int> v;
    for (int i=1; i<=6; i++) v.push_back(i);
    do
    {
        vector <int> id(7);
        for (int i=0; i<6; i++) id[v[i]] = i+1;
        pos.push_back(id);
        perm.push_back(v);
    }
    while (next_permutation(v.begin(),v.end()));
    for (int a=1; a<=6; a++)
        for (int b=a+1; b<=6; b++)
            for (int c=b+1; c<=6; c++)
    {
        for (int d=1; d<=6; d++) if (d!=a&&d!=b&&d!=c) asks.push_back({d,a,b,c});
        for (int i=-2; i<=0; i++) asks.push_back({i,a,b,c});
    }
    bitset<720> bs;
    for (int i=0; i<720; i++) bs[i] = 1;
    cerr<<perm.size()<<endl;
    bool temp = check(bs,6);
}

void orderCoins()
{
    bitset<720> bs;
    for (int i=0; i<720; i++) bs[i] = 1;
    for (int i=6; i>=1; i--)
    {
        vector <int> v = mp[i][bs];
        int temp = query(v);
        for (int j=0; j<720; j++) if (bs[j]&&query2(j,v)!=temp) bs[j] = 0;
    }
    int res[6];
    int it = -1;
    for (int i=0; i<720; i++) if (bs[i]) it = i;
    for (int i=0; i<6; i++) res[i] = perm[it][i];
    answer(res);
}

Compilation message (stderr)

scales.cpp: In function 'bool check(std::bitset<720>, int)':
scales.cpp:49:29: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |             if (bs2.count() > lt3[level-1])
      |                 ~~~~~~~~~~~~^~~~~~~~~~~~~~
scales.cpp:40:9: warning: unused variable 'num' [-Wunused-variable]
   40 |     int num = 0;
      |         ^~~
scales.cpp: In function 'void init(int)':
scales.cpp:96:10: warning: unused variable 'temp' [-Wunused-variable]
   96 |     bool temp = check(bs,6);
      |          ^~~~
scales.cpp:72:15: warning: unused parameter 'test' [-Wunused-parameter]
   72 | void init(int test)
      |           ~~~~^~~~

• Subtask 1: 100 / 100