//#define local
#ifndef local
#include "scales.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
mt19937 rng(1);
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
return abs(temp) + l;
}
int cnt;
int nxt[N][3];
int endd[N];
int perm[721][7];
struct ope{
int type;
int a, b, c, d;
ope(){}
ope(int _type, int _a, int _b, int _c): type(_type), a(_a), b(_b), c(_c){}
ope(int _type, int _a, int _b, int _c, int _d): type(_type), a(_a), b(_b), c(_c), d(_d){}
};
ope todo[N];
vector<ope> opes;
bool bt(int node, vector<int> index){
// cout << node << " " << index.size();
// cout << "\n";
if(index.size() <= 1){
if(index.size() == 1) endd[node] = index[0];
return 1;
}
int sz = (index.size() + 1) / 3;
// iii arr;
// int type;
for(auto it : opes){
vector<int> v1, v2, v3;
for(auto it2 : index){
if(it.type == 1){// maximum
int temp = max({perm[it2][it.a], perm[it2][it.b], perm[it2][it.c]});
// cout << "OKOKOK " << temp << "\n";
if(perm[it2][it.a] == temp) v1.pb(it2);
else if(perm[it2][it.b] == temp) v2.pb(it2);
else v3.pb(it2);
}
else if(it.type == 2){//median
int temp = max({perm[it2][it.a], perm[it2][it.b], perm[it2][it.c]}) + min({perm[it2][it.a], perm[it2][it.b], perm[it2][it.c]});
temp = perm[it2][it.a] + perm[it2][it.b] + perm[it2][it.c] - temp;
if(perm[it2][it.a] == temp) v1.pb(it2);
else if(perm[it2][it.b] == temp) v2.pb(it2);
else v3.pb(it2);
}
else if(it.type == 3){// minimum
int temp = min({perm[it2][it.a], perm[it2][it.b], perm[it2][it.c]});
if(perm[it2][it.a] == temp) v1.pb(it2);
else if(perm[it2][it.b] == temp) v2.pb(it2);
else v3.pb(it2);
}
else{
int temp = max({perm[it2][it.a], perm[it2][it.b], perm[it2][it.c]});
if(temp < perm[it2][it.d]){
temp = min({perm[it2][it.a], perm[it2][it.b], perm[it2][it.c]});
if(perm[it2][it.a] == temp) v1.pb(it2);
else if(perm[it2][it.b] == temp) v2.pb(it2);
else v3.pb(it2);
}
else{
if(perm[it2][it.a] > perm[it2][it.d] && perm[it2][it.a] < temp) temp = perm[it2][it.a];
if(perm[it2][it.b] > perm[it2][it.d] && perm[it2][it.b] < temp) temp = perm[it2][it.b];
if(perm[it2][it.c] > perm[it2][it.d] && perm[it2][it.c] < temp) temp = perm[it2][it.c];
if(perm[it2][it.a] == temp) v1.pb(it2);
else if(perm[it2][it.b] == temp) v2.pb(it2);
else v3.pb(it2);
}
}
}
if(max({v1.size(), v2.size(), v3.size()}) > sz) continue;
for(int i = 0; i < 3; i++){
cnt++;
nxt[node][i] = cnt;
}
bool temp = 1;
int lst = cnt;
temp &= bt(lst - 2, v1);
temp &= bt(lst - 1, v2);
temp &= bt(lst, v3);
// break;
if(temp){
nxt[node][0] = lst - 2;
nxt[node][1] = lst - 1;
nxt[node][2] = lst;
// cout << node << " " << it.type << " " << it.a << " " << it.b << " " << it.c << " " << it.d << "\n";
todo[node] = it;
return 1;
}
}
return 0;
}
void init(int tt){
int arr[7];
for(int i = 1; i <= 6; i++) arr[i] = i;
int t = 0;
vector<int> per;
do{
t++;
for(int i = 1; i <= 6; i++) perm[t][i] = arr[i];
per.pb(t);
// for(int i = 1; i <= 6; i++) cout << arr[i] << " ";
// cout << "\n";
}while(next_permutation(arr + 1, arr + 7));
for(int i = 1; i <= 6; i++){
for(int j = i + 1; j <= 6; j++){
for(int k = j + 1; k <= 6; k++){
for(int h = 1; h <= 3; h++) opes.pb({h, i, j, k});
for(int h = 1; h <= 6; h++){
if(h == i || h == j || h == k) continue;
opes.pb({4, i, j, k, h});
}
}
}
}
cnt = 1;
assert(bt(1, per));
//cout << bt(1, per) << "\n";
}
void orderCoins(){
int itr = 1;
while(1){
//cout << itr << "\n";
// cout << todo[itr].type << " " << todo[itr].a << " " << todo[itr].b << " " << todo[itr].c << " " << todo[itr].d << "\n";
if(endd[itr]){
int arr[6];
for(int i = 1; i <= 6; i++) arr[perm[endd[itr]][i] - 1] = i;
answer(arr);
return;
}
if(todo[itr].type == 1){
int t = getHeaviest(todo[itr].a, todo[itr].b, todo[itr].c);
// cout << "OKOKOK " << t << "\n";
if(t == todo[itr].a) itr = nxt[itr][0];
else if(t == todo[itr].b) itr = nxt[itr][1];
else itr = nxt[itr][2];
}
else if(todo[itr].type == 2){
int t = getMedian(todo[itr].a, todo[itr].b, todo[itr].c);
// cout << t << "\n";
if(t == todo[itr].a) itr = nxt[itr][0];
else if(t == todo[itr].b) itr = nxt[itr][1];
else itr = nxt[itr][2];
}
else if(todo[itr].type == 3){
int t = getLightest(todo[itr].a, todo[itr].b, todo[itr].c);
if(t == todo[itr].a) itr = nxt[itr][0];
else if(t == todo[itr].b) itr = nxt[itr][1];
else itr = nxt[itr][2];
}
else{
int t = getNextLightest(todo[itr].a, todo[itr].b, todo[itr].c, todo[itr].d);
if(t == todo[itr].a) itr = nxt[itr][0];
else if(t == todo[itr].b) itr = nxt[itr][1];
else itr = nxt[itr][2];
}
}
}
//#define local
#ifdef local
void process(){
init(1);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
process();
/*
int t;
cin >> t;
while(t--) process();*/
}
#endif
Compilation message
scales.cpp:22:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
22 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
scales.cpp: In function 'int rnd(int, int)':
scales.cpp:27:19: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
27 | int temp = rng() % (r - l + 1);
| ~~~~~~^~~~~~~~~~~~~
scales.cpp: In function 'bool bt(int, std::vector<int>)':
scales.cpp:56:30: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
56 | int sz = (index.size() + 1) / 3;
| ~~~~~~~~~~~~~~~~~~~^~~
scales.cpp:100:45: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
100 | if(max({v1.size(), v2.size(), v3.size()}) > sz) continue;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
scales.cpp: In function 'void init(int)':
scales.cpp:123:15: warning: unused parameter 'tt' [-Wunused-parameter]
123 | void init(int tt){
| ~~~~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
340 KB |
Output is correct |
2 |
Correct |
23 ms |
376 KB |
Output is correct |
3 |
Correct |
24 ms |
412 KB |
Output is correct |
4 |
Correct |
24 ms |
408 KB |
Output is correct |
5 |
Correct |
23 ms |
400 KB |
Output is correct |
6 |
Correct |
26 ms |
400 KB |
Output is correct |
7 |
Correct |
24 ms |
340 KB |
Output is correct |
8 |
Correct |
25 ms |
340 KB |
Output is correct |
9 |
Correct |
23 ms |
384 KB |
Output is correct |
10 |
Correct |
24 ms |
388 KB |
Output is correct |
11 |
Correct |
23 ms |
404 KB |
Output is correct |
12 |
Correct |
23 ms |
408 KB |
Output is correct |
13 |
Correct |
24 ms |
340 KB |
Output is correct |
14 |
Correct |
24 ms |
384 KB |
Output is correct |
15 |
Correct |
24 ms |
420 KB |
Output is correct |
16 |
Correct |
24 ms |
364 KB |
Output is correct |
17 |
Correct |
23 ms |
404 KB |
Output is correct |
18 |
Correct |
24 ms |
340 KB |
Output is correct |
19 |
Correct |
23 ms |
404 KB |
Output is correct |
20 |
Correct |
24 ms |
392 KB |
Output is correct |
21 |
Correct |
26 ms |
508 KB |
Output is correct |
22 |
Correct |
23 ms |
392 KB |
Output is correct |
23 |
Correct |
23 ms |
340 KB |
Output is correct |
24 |
Correct |
24 ms |
376 KB |
Output is correct |
25 |
Correct |
23 ms |
340 KB |
Output is correct |
26 |
Correct |
24 ms |
468 KB |
Output is correct |
27 |
Correct |
25 ms |
400 KB |
Output is correct |
28 |
Correct |
24 ms |
340 KB |
Output is correct |
29 |
Correct |
23 ms |
376 KB |
Output is correct |
30 |
Correct |
23 ms |
392 KB |
Output is correct |
31 |
Correct |
24 ms |
396 KB |
Output is correct |
32 |
Correct |
24 ms |
412 KB |
Output is correct |
33 |
Correct |
24 ms |
416 KB |
Output is correct |
34 |
Correct |
24 ms |
396 KB |
Output is correct |
35 |
Correct |
24 ms |
396 KB |
Output is correct |
36 |
Correct |
23 ms |
400 KB |
Output is correct |
37 |
Correct |
25 ms |
380 KB |
Output is correct |
38 |
Correct |
24 ms |
396 KB |
Output is correct |
39 |
Correct |
24 ms |
412 KB |
Output is correct |
40 |
Correct |
24 ms |
400 KB |
Output is correct |