| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 756751 | minhcool | Scales (IOI15_scales) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#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]});
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;
todo[node] = it;
for(int i = 0; i < 3; i++){
cnt++;
nxt[node][i] = cnt;
}
bool temp = 1;
temp &= bt(cnt - 2, v1);
temp &= bt(cnt - 1, v2);
temp &= bt(cnt, v3);
// break;
if(temp) 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});
}
}
}
}
bt(1, per);
//cout << bt(1, per) << "\n";
}
void orderCoins(){
int itr = 1;
while(1){
if(endd[itr]){
int arr[6];
for(int i = 1; i <= 6; i++) arr[i - 1] = perm[endd[itr]][i];
answer(arr);
return;
}
if(todo[itr].type == 1){
int t = getHeaviest(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 if(todo[itr].type == 2){
int t = getMedian(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 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