| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 756801 | minhcool | Scales (IOI15_scales) | C++17 | 26 ms | 508 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#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 (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||