#include "scales.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()
inline int gm(int A, int B, int C) {
if (B < A && A < C)
return 0;
if (C < A && A < B)
return 0;
if (A < B && B < C)
return 1;
if (C < B && B < A)
return 1;
return 2;
}
inline int gh(int A, int B, int C) {
if (A > B && A > C)
return 0;
if (B > A && B > C)
return 1;
return 2;
}
inline int gl(int A, int B, int C) {
if (A < B && A < C)
return 0;
if (B < A && B < C)
return 1;
return 2;
}
inline int gnl(int A, int B, int C, int D) {
int allLess = 1;
if (A > D || B > D || C > D)
allLess = 0;
if (allLess == 1) {
if (A < B && A < C)
return 0;
if (B < A && B < C)
return 1;
return 2;
}
if (A > D) {
if ((A < B || B < D) && (A < C || C < D))
return 0;
}
if (B > D) {
if ((B < A || A < D) && (B < C || C < D))
return 1;
}
return 2;
}
const vvii combis = {{0, 1, 2}, {0, 1, 3}, {0, 1, 4}, {0, 1, 5}, {0, 2, 3}, {0, 2, 4}, {0, 2, 5}, {0, 3, 4}, {0, 3, 5}, {0, 4, 5}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}};
vii cc(1100), tt(1100);
map<int, vii> res;
bool search(vvii &curr, int idx = 1) {
if (curr.size() <= 1) {
if (curr.size() == 1) {
res[idx] = curr[0];
}
return true;
}
rep(i, combis.size()) {
auto &combi = combis[i];
vector<vvii> groups(3);
forin(p, curr) {
groups[gl(p[combi[0]], p[combi[1]], p[combi[2]])].emplace_back(p);
}
int cmax = max(groups[0].size(), max(groups[1].size(), groups[2].size()));
int cmin = min(groups[0].size(), min(groups[1].size(), groups[2].size()));
if (cmax - cmin <= 1) {
cc[idx] = i;
tt[idx] = 0;
if (search(groups[0], 3 * idx - 1) && search(groups[1], 3 * idx) && search(groups[2], 3 * idx + 1)) {
return true;
}
}
groups.assign(3, vvii());
forin(p, curr) {
groups[gm(p[combi[0]], p[combi[1]], p[combi[2]])].emplace_back(p);
}
cmax = max(groups[0].size(), max(groups[1].size(), groups[2].size()));
cmin = min(groups[0].size(), min(groups[1].size(), groups[2].size()));
if (cmax - cmin <= 1) {
cc[idx] = i;
tt[idx] = 1;
if (search(groups[0], 3 * idx - 1) && search(groups[1], 3 * idx) && search(groups[2], 3 * idx + 1)) {
return true;
}
}
groups.assign(3, vvii());
forin(p, curr) {
groups[gh(p[combi[0]], p[combi[1]], p[combi[2]])].emplace_back(p);
}
cmax = max(groups[0].size(), max(groups[1].size(), groups[2].size()));
cmin = min(groups[0].size(), min(groups[1].size(), groups[2].size()));
if (cmax - cmin <= 1) {
cc[idx] = i;
tt[idx] = 2;
if (search(groups[0], 3 * idx - 1) && search(groups[1], 3 * idx) && search(groups[2], 3 * idx + 1)) {
return true;
}
}
groups.assign(3, vvii());
forin(p, curr) {
groups[gnl(p[combi[0]], p[combi[1]], p[combi[2]], p[combis[19 - i][0]])].emplace_back(p);
}
cmax = max(groups[0].size(), max(groups[1].size(), groups[2].size()));
cmin = min(groups[0].size(), min(groups[1].size(), groups[2].size()));
if (cmax - cmin <= 1) {
cc[idx] = i;
tt[idx] = 3;
if (search(groups[0], 3 * idx - 1) && search(groups[1], 3 * idx) && search(groups[2], 3 * idx + 1)) {
return true;
}
}
groups.assign(3, vvii());
forin(p, curr) {
groups[gnl(p[combi[0]], p[combi[1]], p[combi[2]], p[combis[19 - i][1]])].emplace_back(p);
}
cmax = max(groups[0].size(), max(groups[1].size(), groups[2].size()));
cmin = min(groups[0].size(), min(groups[1].size(), groups[2].size()));
if (cmax - cmin <= 1) {
cc[idx] = i;
tt[idx] = 4;
if (search(groups[0], 3 * idx - 1) && search(groups[1], 3 * idx) && search(groups[2], 3 * idx + 1)) {
return true;
}
}
groups.assign(3, vvii());
forin(p, curr) {
groups[gnl(p[combi[0]], p[combi[1]], p[combi[2]], p[combis[19 - i][2]])].emplace_back(p);
}
cmax = max(groups[0].size(), max(groups[1].size(), groups[2].size()));
cmin = min(groups[0].size(), min(groups[1].size(), groups[2].size()));
if (cmax - cmin <= 1) {
cc[idx] = i;
tt[idx] = 5;
if (search(groups[0], 3 * idx - 1) && search(groups[1], 3 * idx) && search(groups[2], 3 * idx + 1)) {
return true;
}
}
}
return false;
}
void init(int T) {
vvii curr;
vii x = {1, 2, 3, 4, 5, 6};
int a = getLightest(1, 2, 3) - 1, b = getHeaviest(4, 5, 6) - 4;
do {
curr.emplace_back(x);
} while(next_permutation(all(x)));
search(curr);
}
void orderCoins() {
int idx = 1;
while (res.find(idx) == res.end()) {
auto combi = combis[cc[idx]];
int bt = tt[idx];
if (bt == 0) {
int ans = getLightest(combi[0] + 1, combi[1] + 1, combi[2] + 1);
if (ans == combi[0] + 1) {
idx = 3 * idx - 1;
} else if (ans == combi[1] + 1) {
idx = 3 * idx;
} else {
idx = 3 * idx + 1;
}
} else if (bt == 1) {
int ans = getMedian(combi[0] + 1, combi[1] + 1, combi[2] + 1);
if (ans == combi[0] + 1) {
idx = 3 * idx - 1;
} else if (ans == combi[1] + 1) {
idx = 3 * idx;
} else {
idx = 3 * idx + 1;
}
} else if (bt == 2) {
int ans = getHeaviest(combi[0] + 1, combi[1] + 1, combi[2] + 1);
if (ans == combi[0] + 1) {
idx = 3 * idx - 1;
} else if (ans == combi[1] + 1) {
idx = 3 * idx;
} else {
idx = 3 * idx + 1;
}
} else {
int d = combis[19 - cc[idx]][bt - 3];
int ans = getNextLightest(combi[0] + 1, combi[1] + 1, combi[2] + 1, d + 1);
if (ans == combi[0] + 1) {
idx = 3 * idx - 1;
} else if (ans == combi[1] + 1) {
idx = 3 * idx;
} else {
idx = 3 * idx + 1;
}
}
}
int res2[] = {0, 0, 0, 0, 0, 0};
rep(i, 6) {
res2[res[idx][i] - 1] = i + 1;
}
answer(res2);
}
Compilation message
scales.cpp: In function 'bool search(vvii&, int)':
scales.cpp:105:23: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
105 | int cmax = max(groups[0].size(), max(groups[1].size(), groups[2].size()));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:106:23: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
106 | int cmin = min(groups[0].size(), min(groups[1].size(), groups[2].size()));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:108:23: warning: conversion from 'll' {aka 'long long int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
108 | cc[idx] = i;
| ^
scales.cpp:119:19: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
119 | cmax = max(groups[0].size(), max(groups[1].size(), groups[2].size()));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:120:19: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
120 | cmin = min(groups[0].size(), min(groups[1].size(), groups[2].size()));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:122:23: warning: conversion from 'll' {aka 'long long int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
122 | cc[idx] = i;
| ^
scales.cpp:133:19: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
133 | cmax = max(groups[0].size(), max(groups[1].size(), groups[2].size()));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:134:19: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
134 | cmin = min(groups[0].size(), min(groups[1].size(), groups[2].size()));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:136:23: warning: conversion from 'll' {aka 'long long int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
136 | cc[idx] = i;
| ^
scales.cpp:147:19: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
147 | cmax = max(groups[0].size(), max(groups[1].size(), groups[2].size()));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:148:19: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
148 | cmin = min(groups[0].size(), min(groups[1].size(), groups[2].size()));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:150:23: warning: conversion from 'll' {aka 'long long int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
150 | cc[idx] = i;
| ^
scales.cpp:161:19: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
161 | cmax = max(groups[0].size(), max(groups[1].size(), groups[2].size()));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:162:19: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
162 | cmin = min(groups[0].size(), min(groups[1].size(), groups[2].size()));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:164:23: warning: conversion from 'll' {aka 'long long int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
164 | cc[idx] = i;
| ^
scales.cpp:175:19: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
175 | cmax = max(groups[0].size(), max(groups[1].size(), groups[2].size()));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:176:19: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
176 | cmin = min(groups[0].size(), min(groups[1].size(), groups[2].size()));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:178:23: warning: conversion from 'll' {aka 'long long int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
178 | cc[idx] = i;
| ^
scales.cpp: In function 'void init(int)':
scales.cpp:191:9: warning: unused variable 'a' [-Wunused-variable]
191 | int a = getLightest(1, 2, 3) - 1, b = getHeaviest(4, 5, 6) - 4;
| ^
scales.cpp:191:39: warning: unused variable 'b' [-Wunused-variable]
191 | int a = getLightest(1, 2, 3) - 1, b = getHeaviest(4, 5, 6) - 4;
| ^
scales.cpp:188:15: warning: unused parameter 'T' [-Wunused-parameter]
188 | void init(int T) {
| ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:244:35: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
244 | res2[res[idx][i] - 1] = i + 1;
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
35 ms |
460 KB |
Output is correct |
| 2 |
Correct |
35 ms |
448 KB |
Output is correct |
| 3 |
Correct |
35 ms |
416 KB |
Output is correct |
| 4 |
Correct |
35 ms |
460 KB |
Output is correct |
| 5 |
Correct |
35 ms |
448 KB |
Output is correct |
| 6 |
Correct |
35 ms |
456 KB |
Output is correct |
| 7 |
Correct |
34 ms |
468 KB |
Output is correct |
| 8 |
Correct |
40 ms |
424 KB |
Output is correct |
| 9 |
Correct |
42 ms |
452 KB |
Output is correct |
| 10 |
Correct |
41 ms |
460 KB |
Output is correct |
| 11 |
Correct |
34 ms |
460 KB |
Output is correct |
| 12 |
Correct |
42 ms |
432 KB |
Output is correct |
| 13 |
Correct |
39 ms |
448 KB |
Output is correct |
| 14 |
Correct |
35 ms |
488 KB |
Output is correct |
| 15 |
Correct |
41 ms |
448 KB |
Output is correct |
| 16 |
Correct |
34 ms |
460 KB |
Output is correct |
| 17 |
Correct |
35 ms |
468 KB |
Output is correct |
| 18 |
Correct |
35 ms |
564 KB |
Output is correct |
| 19 |
Correct |
35 ms |
460 KB |
Output is correct |
| 20 |
Correct |
34 ms |
456 KB |
Output is correct |
| 21 |
Correct |
38 ms |
448 KB |
Output is correct |
| 22 |
Correct |
35 ms |
440 KB |
Output is correct |
| 23 |
Correct |
35 ms |
464 KB |
Output is correct |
| 24 |
Correct |
34 ms |
448 KB |
Output is correct |
| 25 |
Correct |
36 ms |
508 KB |
Output is correct |
| 26 |
Correct |
35 ms |
460 KB |
Output is correct |
| 27 |
Correct |
35 ms |
472 KB |
Output is correct |
| 28 |
Correct |
34 ms |
460 KB |
Output is correct |
| 29 |
Correct |
34 ms |
428 KB |
Output is correct |
| 30 |
Correct |
34 ms |
428 KB |
Output is correct |
| 31 |
Correct |
35 ms |
448 KB |
Output is correct |
| 32 |
Correct |
34 ms |
452 KB |
Output is correct |
| 33 |
Correct |
34 ms |
460 KB |
Output is correct |
| 34 |
Correct |
37 ms |
444 KB |
Output is correct |
| 35 |
Correct |
43 ms |
452 KB |
Output is correct |
| 36 |
Correct |
34 ms |
448 KB |
Output is correct |
| 37 |
Correct |
35 ms |
448 KB |
Output is correct |
| 38 |
Correct |
35 ms |
444 KB |
Output is correct |
| 39 |
Correct |
35 ms |
436 KB |
Output is correct |
| 40 |
Correct |
36 ms |
440 KB |
Output is correct |
