Submission #551764

#	Time	Username	Problem	Language	Result	Execution time	Memory
551764		elazarkoren	Scales (IOI15_scales)	C++17	100 / 100	469 ms	7144 KiB

scales

#include <bits/stdc++.h>
#include "scales.h"
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
 
mt19937 rng(time(0));
 
map<vvi, pair<int, vi>> startegy_tree;
//type 1 = light,
//     2 = heavy,
//     3 = med,
//     4 = next
 
bool Solve(vvi &permutations, int x) {
    if (permutations.size() <= 1) return true;
    int log3 = 0;
    int n = permutations.size();
    for (int i = 1; i < n; i *= 3, log3++);
  	chkmax(x, 6 - log3);
    if (x + log3 > 6) return false;
    sort(all(permutations));
    if (startegy_tree.count(permutations)) return true;
    for (int a = 1; a <= 6; a++) {
        for (int b = a + 1; b <= 6; b++) {
            for (int c = b + 1; c <= 6; c++) {
                vvi v1, v2, v3;
                for (vi &v : permutations) {
                    int ind1, ind2, ind3;
                    for (ind1 = 0; v[ind1] != a; ind1++);
                    for (ind2 = 0; v[ind2] != b; ind2++);
                    for (ind3 = 0; v[ind3] != c; ind3++);
                    int i = min({ind1, ind2, ind3});
                    if (i == ind1) v1.push_back(v);
                    else if (i == ind2) v2.push_back(v);
                    else v3.push_back(v);
                }
                if (Solve(v1, x + 1) && Solve(v2, x + 1) && Solve(v3, x + 1)) {
                    if (!x) {
                        cout << "";
                    }
                    startegy_tree[permutations] = {1, {a, b, c}};
                    return true;
                }
            }
        }
    }
    for (int a = 1; a <= 6; a++) {
        for (int b = a + 1; b <= 6; b++) {
            for (int c = b + 1; c <= 6; c++) {
                vvi v1, v2, v3;
                for (vi &v : permutations) {
                    int ind1, ind2, ind3;
                    for (ind1 = 0; v[ind1] != a; ind1++);
                    for (ind2 = 0; v[ind2] != b; ind2++);
                    for (ind3 = 0; v[ind3] != c; ind3++);
                    int i = max({ind1, ind2, ind3});
                    if (i == ind1) v1.push_back(v);
                    else if (i == ind2) v2.push_back(v);
                    else v3.push_back(v);
                }
                if (Solve(v1, x + 1) && Solve(v2, x + 1) && Solve(v3, x + 1)) {
                    if (!x) {
                        cout << "";
                    }
                    startegy_tree[permutations] = {2, {a, b, c}};
                    return true;
                }
            }
        }
    }
    for (int a = 1; a <= 6; a++) {
        for (int b = a + 1; b <= 6; b++) {
            for (int c = b + 1; c <= 6; c++) {
                vvi v1, v2, v3;
                for (vi &v : permutations) {
                    int ind1, ind2, ind3;
                    for (ind1 = 0; v[ind1] != a; ind1++);
                    for (ind2 = 0; v[ind2] != b; ind2++);
                    for (ind3 = 0; v[ind3] != c; ind3++);
                    int i = max({ind1, ind2, ind3}), j = min({ind1, ind2, ind3});
                    if (i != ind1 && j != ind1) v1.push_back(v);
                    else if (i != ind2 && j != ind2) v2.push_back(v);
                    else v3.push_back(v);
                }
                if (Solve(v1, x + 1) && Solve(v2, x + 1) && Solve(v3, x + 1)) {
                    if (!x) {
                        cout << "";
                    }
                    startegy_tree[permutations] = {3, {a, b, c}};
                    return true;
                }
            }
        }
    }
    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) continue;
                    vvi v1, v2, v3;
                    for (vi &v : permutations) {
                        int ind;
                        for (ind = 0; v[ind] != d; ind++);
                        for (; v[ind] != a && v[ind] != b && v[ind] != c; ind++, ind %= 6);
                        if (v[ind] == a) v1.push_back(v);
                        else if (v[ind] == b) v2.push_back(v);
                        else v3.push_back(v);
                    }
                    if (Solve(v1, x + 1) && Solve(v2, x + 1) && Solve(v3, x + 1)) {
                        if (!x) {
                            cout << "";
                        }
                        startegy_tree[permutations] = {4, {a, b, c, d}};
                        return true;
                    }
                }
            }
        }
    }
    if (!x) {
        cout << "";
    }
    return false;
}
 
void init(int T) {
    vvi permutations;
    vi v = {1, 2, 3, 4, 5, 6};
    do {
        permutations.push_back(v);
    } while (next_permutation(all(v)));
    Solve(permutations, 0);
}
 
map<vi, int> asksLight;
int queryLight(int a, int b, int c) {
    vi v = {a, b, c};
    sort(all(v));
    if (asksLight.count(v)) return asksLight[v];
    return asksLight[v] = getLightest(a, b, c);
}
 
map<vi, int> asksHeavy;
int queryHeavy(int a, int b, int c) {
    vi v = {a, b, c};
    sort(all(v));
    if (asksHeavy.count(v)) return asksHeavy[v];
    return asksHeavy[v] = getHeaviest(a, b, c);
}
 
map<vi, int> asksMed;
int queryMed(int a, int b, int c) {
    vi v = {a, b, c};
    sort(all(v));
    if (asksMed.count(v)) return asksMed[v];
    return asksMed[v] = getMedian(a, b, c);
}
 
map<vi, int> asksNext;
int queryNext(int a, int b, int c, int d) {
    vi v = {a, b, c};
    sort(all(v));
    v.push_back(d);
    if (asksNext.count(v)) return asksNext[v];
    return asksNext[v] = getNextLightest(a, b, c, d);
}
 
void orderCoins() {
    int w[] = {1, 2, 3, 4, 5, 6};
    asksLight.clear();
    asksHeavy.clear();
    asksMed.clear();
    asksNext.clear();
    vvi permutations;
    vi v = {1, 2, 3, 4, 5, 6};
    do {
        permutations.push_back(v);
    } while (next_permutation(all(v)));
    while (permutations.size() > 1) {
        int n = permutations.size();
        sort(all(permutations));
        auto [type, v] = startegy_tree[permutations];
        int a = v[0], b = v[1], c = v[2];
        vvi next;
        if (type == 1) {
            int x = queryLight(a, b, c);
            for (vi &v : permutations) {
                int ind1, ind2, ind3;
                for (ind1 = 0; v[ind1] != a; ind1++);
                for (ind2 = 0; v[ind2] != b; ind2++);
                for (ind3 = 0; v[ind3] != c; ind3++);
                if (v[min({ind1, ind2, ind3})] == x) next.push_back(v);
            }
        } else if (type == 2) {
            int x = queryHeavy(a, b, c);
            for (vi &v : permutations) {
                int ind1, ind2, ind3;
                for (ind1 = 0; v[ind1] != a; ind1++);
                for (ind2 = 0; v[ind2] != b; ind2++);
                for (ind3 = 0; v[ind3] != c; ind3++);
                if (v[max({ind1, ind2, ind3})] == x) next.push_back(v);
            }
        } else if (type == 3) {
            int x = queryMed(a, b, c);
            if (x == b) swap(a, b);
            if (x == c) swap(a, c);
            for (vi &v : permutations) {
                int ind1, ind2, ind3;
                for (ind1 = 0; v[ind1] != a; ind1++);
                for (ind2 = 0; v[ind2] != b; ind2++);
                for (ind3 = 0; v[ind3] != c; ind3++);
                if (ind1 != max({ind1, ind2, ind3}) && ind1 != min({ind1, ind2, ind3})) next.push_back(v);
            }
        } else {
            int d = v[3];
            int x = queryNext(a, b, c, d);
            for (vi &v : permutations) {
                int ind;
                for (ind = 0; v[ind] != d; ind++);
                for (; v[ind] != a && v[ind] != b && v[ind] != c; ind++, ind %= 6);
                if (v[ind] == x) next.push_back(v);
            }
        }
        swap(permutations, next);
    }
    for (int i = 0; i < 6; i++) w[i] = permutations[0][i];
    answer(w);
}

Compilation message (stderr)

scales.cpp: In function 'bool Solve(vvi&, int)':
scales.cpp:26:30: warning: conversion from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   26 |     int n = permutations.size();
      |             ~~~~~~~~~~~~~~~~~^~
scales.cpp: In function 'void init(int)':
scales.cpp:135:15: warning: unused parameter 'T' [-Wunused-parameter]
  135 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:189:34: warning: conversion from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  189 |         int n = permutations.size();
      |                 ~~~~~~~~~~~~~~~~~^~
scales.cpp:191:21: warning: declaration of 'v' shadows a previous local [-Wshadow]
  191 |         auto [type, v] = startegy_tree[permutations];
      |                     ^
scales.cpp:184:8: note: shadowed declaration is here
  184 |     vi v = {1, 2, 3, 4, 5, 6};
      |        ^
scales.cpp:196:22: warning: declaration of 'v' shadows a previous local [-Wshadow]
  196 |             for (vi &v : permutations) {
      |                      ^
scales.cpp:191:21: note: shadowed declaration is here
  191 |         auto [type, v] = startegy_tree[permutations];
      |                     ^
scales.cpp:205:22: warning: declaration of 'v' shadows a previous local [-Wshadow]
  205 |             for (vi &v : permutations) {
      |                      ^
scales.cpp:191:21: note: shadowed declaration is here
  191 |         auto [type, v] = startegy_tree[permutations];
      |                     ^
scales.cpp:216:22: warning: declaration of 'v' shadows a previous local [-Wshadow]
  216 |             for (vi &v : permutations) {
      |                      ^
scales.cpp:191:21: note: shadowed declaration is here
  191 |         auto [type, v] = startegy_tree[permutations];
      |                     ^
scales.cpp:226:22: warning: declaration of 'v' shadows a previous local [-Wshadow]
  226 |             for (vi &v : permutations) {
      |                      ^
scales.cpp:191:21: note: shadowed declaration is here
  191 |         auto [type, v] = startegy_tree[permutations];
      |                     ^
scales.cpp:189:13: warning: unused variable 'n' [-Wunused-variable]
  189 |         int n = permutations.size();
      |             ^

• Subtask 1: 100 / 100