#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> all_strats;
typedef pair<int, int> pii;
bool vis[6];
int pow3[10];
void make_strats(vector<int> &v) {
if (v.size() == 6) {
all_strats.push_back(v);
return;
}
for (int i = 0; i < 6; i++) {
if (vis[i]) continue;
vis[i] = 1;
v.push_back(i);
make_strats(v);
v.pop_back();
vis[i] = 0;
}
}
int light(int a, int b, int c, vector<int> &v) {
int s = a;
if (v[b] < v[s]) s = b;
if (v[c] < v[s]) s = c;
return s;
}
int heavy(int a, int b, int c, vector<int> &v) {
int s = a;
if (v[b] > v[s]) s = b;
if (v[c] > v[s]) s = c;
return s;
}
int med(int a, int b, int c, vector<int> &v) {
int l = light(a, b, c, v);
int h = heavy(a, b, c, v);
return a^b^c^l^h;
// if (l == b) {
// swap(a, b);
// }
// if (l == c) swap(a, c);
// if (v[b] < v[c]) return b;
// return c;
}
int next_light(int a, int b, int c, int d, vector<int> &v) {
vector<pii> elems;
elems.push_back(pii(v[a], a));
elems.push_back(pii(v[b], b));
elems.push_back(pii(v[c], c));
elems.push_back(pii(v[d], d));
sort(elems.begin(), elems.end());
int p;
for (int i = 0; i < 4; i++) {
if (elems[i].second == d) {
p = i;
break;
}
}
if (p == 3) return elems[0].second;
return elems[p+1].second;
}
class query {
public:
vector<int> nxt_states;
int tp;
vector<int> queried;
vector<int> perm;
query(vector<int> &nxt, int t = -1, int a = -1, int b = -1, int c = -1, int d = -1) {
if (c == -1) {
tp = -1;
perm = nxt;
return;
}
nxt_states = nxt;
tp = t;
queried.push_back(a+1);
queried.push_back(b+1);
queried.push_back(c+1);
if (t == 3) queried.push_back(d+1);
}
};
vector<query> query_res;
bool find_split(vector<int> &strats, int depth = 6) {
if (depth == 0) {
assert(strats.size() <= 1);
if (strats.size() == 1) query_res.push_back(all_strats[strats[0]]);
return 1;
}
for (int a = 0; a < 4; a++) {
for (int b = a+1; b < 5; b++) {
for (int c = b+1; c < 6; c++) {
for (int tp = 0; tp <= 3; tp++) {
for (int d = 0; d < ((tp < 3) ? 1 : 6); d++) {
if (tp == 3 && (d == a || d == b || d == c)) continue;
vector<int> g1;
vector<int> g2;
vector<int> g3;
for (int cur: strats) {
int res;
if (tp == 0) res = light(a, b, c, all_strats[cur]);
if (tp == 1) res = heavy(a, b, c, all_strats[cur]);
if (tp == 2) res = med(a, b, c, all_strats[cur]);
if (tp == 3) res = next_light(a, b, c, d, all_strats[cur]);
if (res == a) g1.push_back(cur);
if (res == b) g2.push_back(cur);
if (res == c) g3.push_back(cur);
}
if (g1.size() > pow3[depth-1] || g2.size() > pow3[depth-1] || g3.size() > pow3[depth-1]) continue;
bool g = 1;
vector<int> ids;
if (!g) continue;
else {
g = find_split(g1, depth-1);
ids.push_back(query_res.size()-1);
}
if (!g) continue;
else {
g = find_split(g2, depth-1);
ids.push_back(query_res.size()-1);
}
if (!g) continue;
else {
g = find_split(g3, depth-1);
ids.push_back(query_res.size()-1);
}
if (g) {
query_res.push_back(query(ids, tp, a, b, c, d));
return 1;
}
}
}
}
}
}
return 0;
}
void init(int t) {
pow3[0] = 1;
for (int i = 1; i < 10; i++) pow3[i] = 3*pow3[i-1];
vector<int> v;
make_strats(v);
vector<int> strats(all_strats.size());
iota(strats.begin(), strats.end(), 0);
find_split(strats);
}
void orderCoins() {
int cur = query_res.size()-1;
for (int i = 0; i < 6; i++) {
int res;
int a = query_res[cur].queried[0],
b = query_res[cur].queried[1],
c = query_res[cur].queried[2],
d = (query_res[cur].tp == 3 ? query_res[cur].queried[3] : 0);
if (query_res[cur].tp == 0) res = getLightest(a, b, c);
if (query_res[cur].tp == 1) res = getHeaviest(a, b, c);
if (query_res[cur].tp == 2) res = getMedian(a, b, c);
if (query_res[cur].tp == 3) res = getNextLightest(a, b, c, d);
if (res == a) cur = query_res[cur].nxt_states[0];
if (res == b) cur = query_res[cur].nxt_states[1];
if (res == c) cur = query_res[cur].nxt_states[2];
}
int ans[6];
for (int i = 0; i < 6; i++) ans[query_res[cur].perm[i]] = i+1;
answer(ans);
}
Compilation message
scales.cpp: In function 'bool find_split(std::vector<int>&, int)':
scales.cpp:119:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
119 | if (g1.size() > pow3[depth-1] || g2.size() > pow3[depth-1] || g3.size() > pow3[depth-1]) continue;
| ~~~~~~~~~~^~~~~~~~~~~~~~~
scales.cpp:119:50: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
119 | if (g1.size() > pow3[depth-1] || g2.size() > pow3[depth-1] || g3.size() > pow3[depth-1]) continue;
| ~~~~~~~~~~^~~~~~~~~~~~~~~
scales.cpp:119:79: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
119 | if (g1.size() > pow3[depth-1] || g2.size() > pow3[depth-1] || g3.size() > pow3[depth-1]) continue;
| ~~~~~~~~~~^~~~~~~~~~~~~~~
scales.cpp:125:38: warning: conversion from 'std::vector<query>::size_type' {aka 'long unsigned int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
125 | ids.push_back(query_res.size()-1);
| ~~~~~~~~~~~~~~~~^~
scales.cpp:130:38: warning: conversion from 'std::vector<query>::size_type' {aka 'long unsigned int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
130 | ids.push_back(query_res.size()-1);
| ~~~~~~~~~~~~~~~~^~
scales.cpp:135:38: warning: conversion from 'std::vector<query>::size_type' {aka 'long unsigned int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
135 | ids.push_back(query_res.size()-1);
| ~~~~~~~~~~~~~~~~^~
scales.cpp: In function 'void init(int)':
scales.cpp:149:15: warning: unused parameter 't' [-Wunused-parameter]
149 | void init(int t) {
| ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:160:28: warning: conversion from 'std::vector<query>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
160 | int cur = query_res.size()-1;
| ~~~~~~~~~~~~~~~~^~
scales.cpp:173:3: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
173 | if (res == c) cur = query_res[cur].nxt_states[2];
| ^~
scales.cpp: In function 'int next_light(int, int, int, int, std::vector<int>&)':
scales.cpp:68:16: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
68 | return elems[p+1].second;
| ~^~
scales.cpp: In function 'bool find_split(std::vector<int>&, int)':
scales.cpp:116:8: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
116 | if (res == b) g2.push_back(cur);
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
38 ms |
624 KB |
Output is correct |
| 2 |
Correct |
38 ms |
624 KB |
Output is correct |
| 3 |
Correct |
38 ms |
648 KB |
Output is correct |
| 4 |
Correct |
38 ms |
636 KB |
Output is correct |
| 5 |
Correct |
38 ms |
648 KB |
Output is correct |
| 6 |
Correct |
38 ms |
628 KB |
Output is correct |
| 7 |
Correct |
38 ms |
628 KB |
Output is correct |
| 8 |
Correct |
38 ms |
600 KB |
Output is correct |
| 9 |
Correct |
40 ms |
708 KB |
Output is correct |
| 10 |
Correct |
38 ms |
588 KB |
Output is correct |
| 11 |
Correct |
38 ms |
632 KB |
Output is correct |
| 12 |
Correct |
38 ms |
616 KB |
Output is correct |
| 13 |
Correct |
38 ms |
644 KB |
Output is correct |
| 14 |
Correct |
38 ms |
652 KB |
Output is correct |
| 15 |
Correct |
38 ms |
588 KB |
Output is correct |
| 16 |
Correct |
38 ms |
652 KB |
Output is correct |
| 17 |
Correct |
39 ms |
744 KB |
Output is correct |
| 18 |
Correct |
38 ms |
588 KB |
Output is correct |
| 19 |
Correct |
38 ms |
604 KB |
Output is correct |
| 20 |
Correct |
38 ms |
612 KB |
Output is correct |
| 21 |
Correct |
43 ms |
588 KB |
Output is correct |
| 22 |
Correct |
38 ms |
644 KB |
Output is correct |
| 23 |
Correct |
38 ms |
592 KB |
Output is correct |
| 24 |
Correct |
38 ms |
616 KB |
Output is correct |
| 25 |
Correct |
38 ms |
628 KB |
Output is correct |
| 26 |
Correct |
39 ms |
588 KB |
Output is correct |
| 27 |
Correct |
38 ms |
596 KB |
Output is correct |
| 28 |
Correct |
38 ms |
604 KB |
Output is correct |
| 29 |
Correct |
38 ms |
628 KB |
Output is correct |
| 30 |
Correct |
38 ms |
596 KB |
Output is correct |
| 31 |
Correct |
38 ms |
616 KB |
Output is correct |
| 32 |
Correct |
38 ms |
624 KB |
Output is correct |
| 33 |
Correct |
38 ms |
548 KB |
Output is correct |
| 34 |
Correct |
38 ms |
608 KB |
Output is correct |
| 35 |
Correct |
40 ms |
740 KB |
Output is correct |
| 36 |
Correct |
38 ms |
588 KB |
Output is correct |
| 37 |
Correct |
38 ms |
628 KB |
Output is correct |
| 38 |
Correct |
38 ms |
620 KB |
Output is correct |
| 39 |
Correct |
38 ms |
624 KB |
Output is correct |
| 40 |
Correct |
38 ms |
624 KB |
Output is correct |
