Submission #706664

#	Time	Username	Problem	Language	Result	Execution time	Memory
706664		marvinthang	Scales (IOI15_scales)	C++17	100 / 100	37 ms	544 KiB

scales

/*************************************
*    author: marvinthang             *
*    created: 06.03.2023 15:25:06    *
*************************************/

#include "scales.h"
#include <bits/stdc++.h>

using namespace std;

#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 

#define Bitset bitset<720>

vector <vector <int>> ask, perms, pos;
int pw3[7];

int Ask(const 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 Ask(int p, vector <int> v) {
    sort(1 + ALL(v), [&] (int a, int b) { return pos[p][a] < pos[p][b]; });
    if (v[0] < 1) return v[1 - v[0]];
    FOR(i, 1, 4) if (pos[p][v[i]] > pos[p][v[0]]) return v[i];
    return v[1];
}

struct Cmp {
    bool operator() (const Bitset &a, const Bitset &b) const {
        REP(i, 720) if (a[i] != b[i]) return a[i] < b[i];
        return false;
    }
};

map <Bitset, vector <int>, Cmp> cache[7];

bool check(Bitset bs, int turn) {
    int cnt = bs.count();
    if (cnt <= 1) return true;
    if (cache[turn].count(bs)) return !cache[turn][bs].empty();
    for (auto v: ask) {
        vector <int> id(7);
        REP(i, 3) id[v[i + 1]] = i;
        vector <Bitset> nxt(3);
        REP(i, 720) if (bs[i]) nxt[id[Ask(i, v)]][i] = 1;
        bool ok = true;
        for (Bitset &b: nxt) if (b.count() > pw3[turn - 1]) {
            ok = false;
            break;
        }
        if (!ok) continue;
        for (Bitset &b: nxt) if (!check(b, turn - 1)) {
            ok = false;
            break;
        }
        if (ok) {
            cache[turn][bs] = v;
            return true;
        }
    }
    cache[turn][bs] = vector<int>{};
    return false;
}

void init(int T) {
    pw3[0] = 1;
    REP(i, 6) pw3[i + 1] = pw3[i] * 3;
    vector <int> v {1, 2, 3, 4, 5, 6};
    do {
        perms.push_back(v);
        pos.push_back(vector<int>(7));
        REP(i, 6) pos.back()[perms.back()[i]] = i;
    } while (next_permutation(ALL(v)));
    FOR(a, 1, 7) FOR(b, a + 1, 7) FOR(c, b + 1, 7) {
        FOR(d, 1, 7) if (d != a && d != b && d != c) ask.push_back(vector<int>{d, a, b, c});
        for (int i: {1, 0, 2}) ask.push_back(vector<int>{-i, a, b, c});
    }
    Bitset bs;
    bs.set();
    check(bs, 6);
}

void orderCoins() {
    Bitset bs;
    bs.set();
    FORD(i, 7, 1) {
        vector <int> v = cache[i][bs];
        int cur = Ask(v);
        REP(i, 720) if (bs[i] && Ask(i, v) != cur) bs[i] = 0;
    }
    int W[6];
    copy(ALL(perms[bs._Find_first()]), W);
    answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'bool check(std::bitset<720>, int)':
scales.cpp:45:23: warning: conversion from 'std::size_t' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   45 |     int cnt = bs.count();
      |               ~~~~~~~~^~
scales.cpp:54:44: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |         for (Bitset &b: nxt) if (b.count() > pw3[turn - 1]) {
      |                                  ~~~~~~~~~~^~~~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:13:48: warning: declaration of '_b' shadows a previous local [-Wshadow]
   13 | #define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i)
      |                                                ^~
scales.cpp:81:18: note: in expansion of macro 'FOR'
   81 |     FOR(a, 1, 7) FOR(b, a + 1, 7) FOR(c, b + 1, 7) {
      |                  ^~~
scales.cpp:13:48: note: shadowed declaration is here
   13 | #define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i)
      |                                                ^~
scales.cpp:81:5: note: in expansion of macro 'FOR'
   81 |     FOR(a, 1, 7) FOR(b, a + 1, 7) FOR(c, b + 1, 7) {
      |     ^~~
scales.cpp:13:48: warning: declaration of '_b' shadows a previous local [-Wshadow]
   13 | #define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i)
      |                                                ^~
scales.cpp:81:35: note: in expansion of macro 'FOR'
   81 |     FOR(a, 1, 7) FOR(b, a + 1, 7) FOR(c, b + 1, 7) {
      |                                   ^~~
scales.cpp:13:48: note: shadowed declaration is here
   13 | #define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i)
      |                                                ^~
scales.cpp:81:18: note: in expansion of macro 'FOR'
   81 |     FOR(a, 1, 7) FOR(b, a + 1, 7) FOR(c, b + 1, 7) {
      |                  ^~~
scales.cpp:13:48: warning: declaration of '_b' shadows a previous local [-Wshadow]
   13 | #define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i)
      |                                                ^~
scales.cpp:82:9: note: in expansion of macro 'FOR'
   82 |         FOR(d, 1, 7) if (d != a && d != b && d != c) ask.push_back(vector<int>{d, a, b, c});
      |         ^~~
scales.cpp:13:48: note: shadowed declaration is here
   13 | #define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i)
      |                                                ^~
scales.cpp:81:35: note: in expansion of macro 'FOR'
   81 |     FOR(a, 1, 7) FOR(b, a + 1, 7) FOR(c, b + 1, 7) {
      |                                   ^~~
scales.cpp:72:15: warning: unused parameter 'T' [-Wunused-parameter]
   72 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:96:13: warning: declaration of 'i' shadows a previous local [-Wshadow]
   96 |         REP(i, 720) if (bs[i] && Ask(i, v) != cur) bs[i] = 0;
      |             ^
scales.cpp:12:39: note: in definition of macro 'REP'
   12 | #define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
      |                                       ^
scales.cpp:93:10: note: shadowed declaration is here
   93 |     FORD(i, 7, 1) {
      |          ^
scales.cpp:14:39: note: in definition of macro 'FORD'
   14 | #define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; )
      |                                       ^

• Subtask 1: 100 / 100