#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
vector<vector<int>> perm;
vector<vector<int>> query;
void init(int T) {
for (int d = 0; d < 6; d++){
for (int i = 0; i < 6; i++){
for (int j = i+1; j < 6; j++){
for (int k = j+1; k < 6; k++){
if (i == d || j == d || k == d) continue;
query.push_back({i, j, k, d});
}
}
}
}
for (auto x: {-2, -3, -1}){
for (int i = 0; i < 6; i++){
for (int j = i+1; j < 6; j++){
for (int k = j+1; k < 6; k++){
query.push_back({i, j, k, x});
}
}
}
}
}
int get(vector<int> a, int x, int y, int z, int idx){
if (perm.size() == 6) debug(x, y, z, idx);
vector<int> tmp = {a[x], a[y], a[z]};
sort(all(tmp));
if (tmp[idx] == a[x]) return 0;
if (tmp[idx] == a[y]) return 1;
if (tmp[idx] == a[z]) return 2;
}
int getnext(vector<int> a, int x, int y, int z, int d){
vector<int> tmp = {a[x], a[y], a[z]};
sort(all(tmp));
int idx = 0;
for (int i = 0; i < 3; i++){
if (tmp[i] > a[d]){
idx = i;
break;
}
}
if (tmp[idx] == a[x]) return 0;
if (tmp[idx] == a[y]) return 1;
if (tmp[idx] == a[z]) return 2;
}
void solve(){
//debug(perm.size());
if (perm.size() == 6){
for (auto x: perm){
for (auto y: x) cerr << y << ' ';
cerr << endl;
}
}
if (perm.size() == 1) return;
int mx = perm.size() + 1;
vector<vector<int>> ans[3];
vector<int> q;
for (auto x: query){
vector<vector<int>> res[3];
for (auto y: perm){
if (x[3] >= 0){
int tmp = getnext(y, x[0], x[1], x[2], x[3]);
res[tmp].push_back(y);
}
else{
int tmp = get(y, x[0], x[1], x[2], -x[3] - 1);
res[tmp].push_back(y);
}
}
if (perm.size() == 6 && x[3] < 0){
// debug(x[0], x[1], x[2], x[3], res[0].size(), res[1].size(), res[2].size());
}
int tmp = max({res[0].size(), res[1].size(), res[2].size()});
if (tmp < mx){
mx = tmp;
for (int i = 0; i < 3; i++){
ans[i] = res[i];
}
q = x;
}
}
assert(mx != perm.size());
if (q[3] >= 0){
int tmp = getNextLightest(q[0]+1, q[1]+1, q[2]+1, q[3]+1) - 1;
for (int i = 0; i < 3; i++){
if (tmp == q[i]) perm = ans[i];
}
}
else{
int tmp;
switch(q[3]){
case -1:
tmp = getLightest(q[0]+1, q[1]+1, q[2]+1)-1;
break;
case -2:
tmp = getMedian(q[0]+1, q[1]+1, q[2]+1)-1;
break;
case -3:
tmp = getHeaviest(q[0]+1, q[1]+1, q[2]+1)-1;
break;
}
for (int i = 0; i < 3; i++){
if (tmp == q[i]) perm = ans[i];
}
}
solve();
}
int cnt = 0;
void orderCoins() {
cnt++;
debug(cnt);
vector<int> tmp = {0, 1, 2, 3, 4, 5};
perm.clear();
do{
perm.push_back(tmp);
} while(next_permutation(all(tmp)));
//debug(perm.size());
solve();
int ans[6];
for (int i = 0; i < 6; i++) ans[perm[0][i]] = i+1;
answer(ans);
}
Compilation message
scales.cpp: In function 'void init(int)':
scales.cpp:29:15: warning: unused parameter 'T' [-Wunused-parameter]
29 | void init(int T) {
| ~~~~^
scales.cpp: In function 'void solve()':
scales.cpp:85:23: warning: conversion from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
85 | int mx = perm.size() + 1;
| ~~~~~~~~~~~~^~~
scales.cpp:103:16: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
103 | int tmp = max({res[0].size(), res[1].size(), res[2].size()});
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from scales.cpp:2:
scales.cpp:112:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | assert(mx != perm.size());
| ~~~^~~~~~~~~~~~~~
scales.cpp: In function 'int get(std::vector<int>, int, int, int, int)':
scales.cpp:54:37: warning: control reaches end of non-void function [-Wreturn-type]
54 | vector<int> tmp = {a[x], a[y], a[z]};
| ^
scales.cpp: In function 'int getnext(std::vector<int>, int, int, int, int)':
scales.cpp:62:37: warning: control reaches end of non-void function [-Wreturn-type]
62 | vector<int> tmp = {a[x], a[y], a[z]};
| ^
scales.cpp: In function 'void solve()':
scales.cpp:133:4: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
133 | if (tmp == q[i]) perm = ans[i];
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
350 ms |
436 KB |
Output is correct |
2 |
Correct |
306 ms |
444 KB |
Output is correct |
3 |
Correct |
337 ms |
448 KB |
Output is correct |
4 |
Correct |
298 ms |
444 KB |
Output is correct |
5 |
Correct |
347 ms |
444 KB |
Output is correct |
6 |
Correct |
294 ms |
452 KB |
Output is correct |
7 |
Correct |
318 ms |
444 KB |
Output is correct |
8 |
Correct |
321 ms |
440 KB |
Output is correct |
9 |
Correct |
311 ms |
444 KB |
Output is correct |
10 |
Correct |
327 ms |
444 KB |
Output is correct |
11 |
Correct |
300 ms |
448 KB |
Output is correct |
12 |
Correct |
338 ms |
444 KB |
Output is correct |
13 |
Correct |
305 ms |
492 KB |
Output is correct |
14 |
Correct |
335 ms |
448 KB |
Output is correct |
15 |
Correct |
300 ms |
452 KB |
Output is correct |
16 |
Correct |
354 ms |
444 KB |
Output is correct |
17 |
Correct |
294 ms |
444 KB |
Output is correct |
18 |
Correct |
325 ms |
444 KB |
Output is correct |
19 |
Correct |
345 ms |
452 KB |
Output is correct |
20 |
Correct |
324 ms |
448 KB |
Output is correct |
21 |
Correct |
323 ms |
448 KB |
Output is correct |
22 |
Correct |
375 ms |
444 KB |
Output is correct |
23 |
Correct |
390 ms |
448 KB |
Output is correct |
24 |
Correct |
325 ms |
340 KB |
Output is correct |
25 |
Correct |
328 ms |
560 KB |
Output is correct |
26 |
Correct |
337 ms |
448 KB |
Output is correct |
27 |
Correct |
356 ms |
572 KB |
Output is correct |
28 |
Correct |
333 ms |
448 KB |
Output is correct |
29 |
Correct |
325 ms |
440 KB |
Output is correct |
30 |
Correct |
335 ms |
436 KB |
Output is correct |
31 |
Correct |
323 ms |
468 KB |
Output is correct |
32 |
Correct |
345 ms |
448 KB |
Output is correct |
33 |
Correct |
318 ms |
452 KB |
Output is correct |
34 |
Correct |
345 ms |
440 KB |
Output is correct |
35 |
Correct |
362 ms |
436 KB |
Output is correct |
36 |
Correct |
343 ms |
448 KB |
Output is correct |
37 |
Correct |
323 ms |
424 KB |
Output is correct |
38 |
Correct |
391 ms |
448 KB |
Output is correct |
39 |
Correct |
343 ms |
444 KB |
Output is correct |
40 |
Correct |
391 ms |
568 KB |
Output is correct |