#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
refs:
edi
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
#include "scales.h"
ll n = 6;
vector<ll> pow3(15);
vector<array<ll,4>> ops;
map< tuple< vector<vector<ll>>, ll, ll>, bool > mp;
bool go(vector<vector<ll>> &a, ll ind, ll m){
// can make m more guesses
if(m < 0) return false;
if(sz(a) > pow3[m]) return false;
if(m == 0) return true;
if(ind >= sz(ops)) return false;
if(mp.count({a,ind,m})) return mp[{a,ind,m}];
// do op
auto [i,j,k,t] = ops[ind];
vector<vector<ll>> v1,v2,v3;
trav(v,a){
if(t == 0){
if(v[i] < v[j] and v[i] < v[k]){
v1.pb(v);
}
else if(v[j] < v[i] and v[j] < v[k]){
v2.pb(v);
}
else{
v3.pb(v);
}
}
else if(t == 1){
if(v[i] > min(v[j],v[k]) and v[i] < max(v[j],v[k])){
v1.pb(v);
}
else if(v[j] > min(v[i],v[k]) and v[j] < max(v[i],v[k])){
v2.pb(v);
}
else{
v3.pb(v);
}
}
else if(t == 2){
if(v[i] > v[j] and v[i] > v[k]){
v1.pb(v);
}
else if(v[j] > v[i] and v[j] > v[k]){
v2.pb(v);
}
else{
v3.pb(v);
}
}
}
bool ans = go(v1,ind+1,m-1)&go(v2,ind+1,m-1)&go(v3,ind+1,m-1);
if(ans) return true;
// skip
ans = go(a,ind+1,m);
return mp[{a,ind,m}] = ans;
}
vector<vector<ll>> adj;
vector<vector<vector<ll>>> here;
vector<ll> op;
void init(int T) {
pow3[0] = 1;
rep1(i,10) pow3[i] = pow3[i-1]*3;
rep(i,n){
for(int j = i+1; j < n; ++j){
for(int k = j+1; k < n; ++k){
rep(t,3){
ops.pb({i,j,k,t});
}
}
}
}
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng(1);
shuffle(all(ops),rng);
vector<vector<ll>> perms;
vector<ll> a(n);
iota(all(a),1);
do{
perms.pb(a);
} while(next_permutation(all(a)));
bool ok = go(perms,0,7);
ll ptr = 0;
auto new_node = [&](vector<vector<ll>> v){
adj.pb(vector<ll>());
here.pb(v);
op.pb(0);
return ptr++;
};
queue<tuple< vector<vector<ll>>, ll, ll, ll>> q;
q.push({perms,0,7,new_node(perms)});
while(!q.empty()){
auto [a,ind,m,u] = q.front();
q.pop();
if(sz(a) <= 1) conts;
assert(m >= 1);
bool ok = false;
for(int opi = ind; opi < sz(ops); ++opi){
auto [i,j,k,t] = ops[opi];
vector<vector<ll>> v1,v2,v3;
trav(v,a){
if(t == 0){
if(v[i] < v[j] and v[i] < v[k]){
v1.pb(v);
}
else if(v[j] < v[i] and v[j] < v[k]){
v2.pb(v);
}
else{
v3.pb(v);
}
}
else if(t == 1){
if(v[i] > min(v[j],v[k]) and v[i] < max(v[j],v[k])){
v1.pb(v);
}
else if(v[j] > min(v[i],v[k]) and v[j] < max(v[i],v[k])){
v2.pb(v);
}
else{
v3.pb(v);
}
}
else if(t == 2){
if(v[i] > v[j] and v[i] > v[k]){
v1.pb(v);
}
else if(v[j] > v[i] and v[j] > v[k]){
v2.pb(v);
}
else{
v3.pb(v);
}
}
}
bool res = go(v1,opi+1,m-1)&go(v2,opi+1,m-1)&go(v3,opi+1,m-1);
if(res){
ok = true;
op[u] = opi;
for(auto v : {v1,v2,v3}){
ll x = new_node(v);
adj[u].pb(x);
q.push({v,opi+1,m-1,x});
}
break;
}
}
}
}
void found(vector<ll> a){
int ans[6];
rep(i,6) ans[a[i]-1] = i+1;
answer(ans);
}
void orderCoins() {
ll u = 0;
while(true){
auto &a = here[u];
if(sz(a) == 1){
found(a[0]);
return;
}
ll ind = op[u];
auto [i,j,k,t] = ops[ind];
i++, j++, k++;
ll res = 0;
if(t == 0){
res = getLightest(i,j,k);
}
else if(t == 1){
res = getMedian(i,j,k);
}
else if(t == 2){
res = getHeaviest(i,j,k);
}
else{
assert(0);
}
if(res == i){
u = adj[u][0];
}
else if(res == j){
u = adj[u][1];
}
else{
u = adj[u][2];
}
}
}
Compilation message
scales.cpp: In function 'void init(int)':
scales.cpp:170:15: warning: declaration of 'a' shadows a previous local [-Wshadow]
170 | auto [a,ind,m,u] = q.front();
| ^
scales.cpp:146:16: note: shadowed declaration is here
146 | vector<ll> a(n);
| ^
scales.cpp:175:14: warning: declaration of 'ok' shadows a previous local [-Wshadow]
175 | bool ok = false;
| ^~
scales.cpp:155:10: note: shadowed declaration is here
155 | bool ok = go(perms,0,7);
| ^~
scales.cpp:177:23: warning: conversion from 'std::tuple_element<0, std::tuple<long long int, long long int, long long int> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
177 | for(int opi = ind; opi < sz(ops); ++opi){
| ^~~
scales.cpp:175:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
175 | bool ok = false;
| ^~
scales.cpp:155:10: warning: unused variable 'ok' [-Wunused-variable]
155 | bool ok = go(perms,0,7);
| ^~
scales.cpp:127:15: warning: unused parameter 'T' [-Wunused-parameter]
127 | void init(int T) {
| ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:254:31: warning: conversion from 'std::tuple_element<0, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
254 | res = getLightest(i,j,k);
| ^
scales.cpp:254:33: warning: conversion from 'std::tuple_element<1, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
254 | res = getLightest(i,j,k);
| ^
scales.cpp:254:35: warning: conversion from 'std::tuple_element<2, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
254 | res = getLightest(i,j,k);
| ^
scales.cpp:257:29: warning: conversion from 'std::tuple_element<0, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
257 | res = getMedian(i,j,k);
| ^
scales.cpp:257:31: warning: conversion from 'std::tuple_element<1, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
257 | res = getMedian(i,j,k);
| ^
scales.cpp:257:33: warning: conversion from 'std::tuple_element<2, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
257 | res = getMedian(i,j,k);
| ^
scales.cpp:260:31: warning: conversion from 'std::tuple_element<0, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
260 | res = getHeaviest(i,j,k);
| ^
scales.cpp:260:33: warning: conversion from 'std::tuple_element<1, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
260 | res = getHeaviest(i,j,k);
| ^
scales.cpp:260:35: warning: conversion from 'std::tuple_element<2, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' may change value [-Wconversion]
260 | res = getHeaviest(i,j,k);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
241 ms |
39252 KB |
Output is partially correct |
| 2 |
Partially correct |
255 ms |
39332 KB |
Output is partially correct |
| 3 |
Partially correct |
260 ms |
39468 KB |
Output is partially correct |
| 4 |
Partially correct |
244 ms |
39176 KB |
Output is partially correct |
| 5 |
Partially correct |
278 ms |
39216 KB |
Output is partially correct |
| 6 |
Partially correct |
276 ms |
39348 KB |
Output is partially correct |
| 7 |
Partially correct |
271 ms |
39256 KB |
Output is partially correct |
| 8 |
Partially correct |
253 ms |
39200 KB |
Output is partially correct |
| 9 |
Partially correct |
258 ms |
39256 KB |
Output is partially correct |
| 10 |
Partially correct |
269 ms |
39068 KB |
Output is partially correct |
| 11 |
Partially correct |
239 ms |
39152 KB |
Output is partially correct |
| 12 |
Partially correct |
242 ms |
39128 KB |
Output is partially correct |
| 13 |
Partially correct |
253 ms |
39252 KB |
Output is partially correct |
| 14 |
Partially correct |
271 ms |
39304 KB |
Output is partially correct |
| 15 |
Partially correct |
244 ms |
39248 KB |
Output is partially correct |
| 16 |
Partially correct |
272 ms |
39252 KB |
Output is partially correct |
| 17 |
Partially correct |
246 ms |
39248 KB |
Output is partially correct |
| 18 |
Partially correct |
267 ms |
39248 KB |
Output is partially correct |
| 19 |
Partially correct |
263 ms |
39404 KB |
Output is partially correct |
| 20 |
Partially correct |
282 ms |
39200 KB |
Output is partially correct |
| 21 |
Partially correct |
251 ms |
39248 KB |
Output is partially correct |
| 22 |
Partially correct |
251 ms |
39248 KB |
Output is partially correct |
| 23 |
Partially correct |
251 ms |
39252 KB |
Output is partially correct |
| 24 |
Partially correct |
277 ms |
39096 KB |
Output is partially correct |
| 25 |
Partially correct |
250 ms |
39152 KB |
Output is partially correct |
| 26 |
Partially correct |
250 ms |
39376 KB |
Output is partially correct |
| 27 |
Partially correct |
261 ms |
39248 KB |
Output is partially correct |
| 28 |
Partially correct |
263 ms |
39128 KB |
Output is partially correct |
| 29 |
Partially correct |
268 ms |
39248 KB |
Output is partially correct |
| 30 |
Partially correct |
269 ms |
39248 KB |
Output is partially correct |
| 31 |
Partially correct |
258 ms |
39248 KB |
Output is partially correct |
| 32 |
Partially correct |
270 ms |
39176 KB |
Output is partially correct |
| 33 |
Partially correct |
251 ms |
39292 KB |
Output is partially correct |
| 34 |
Partially correct |
269 ms |
39252 KB |
Output is partially correct |
| 35 |
Partially correct |
251 ms |
39252 KB |
Output is partially correct |
| 36 |
Partially correct |
267 ms |
39216 KB |
Output is partially correct |
| 37 |
Partially correct |
260 ms |
39244 KB |
Output is partially correct |
| 38 |
Partially correct |
264 ms |
39144 KB |
Output is partially correct |
| 39 |
Partially correct |
271 ms |
39168 KB |
Output is partially correct |
| 40 |
Partially correct |
243 ms |
39244 KB |
Output is partially correct |
