| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 68665 | FLDutchman | 저울 (IOI15_scales) | C++14 | 23 ms | 892 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
typedef int INT;
#define FOR(i,l,r) for(int i = (l); i < (r); i++)
#define fst first
#define snd second
#define pb push_back
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
vi op;
vvi args;
// this corresponds to the relative weight of the coins
vvi perms;
vi ans;
int pows[] = {1,3,9,27,81,243,729};
int heavy(int i, int A, int B, int C){
vi &p = perms[i];
if(p[A] > p[B] and p[A] > p[C]) return 0;
if(p[B] > p[A] and p[B] > p[C]) return 1;
if(p[C] > p[B] and p[C] > p[A]) return 2;
}
int light(int i, int A, int B, int C){
vi &p = perms[i];
if(p[A] < p[B] and p[A] < p[C]) return 0;
if(p[B] < p[A] and p[B] < p[C]) return 1;
if(p[C] < p[B] and p[C] < p[A]) return 2;
}
int median(int i, int A, int B, int C){
vi &p = perms[i];
vi arr(3, 0);
arr[0] = A; arr[1] = B; arr[2] = C;
sort(arr.begin(), arr.end(), [&p] (int i, int j) {return p[i] < p[j];});
if(arr[1] == A) return 0;
if(arr[1] == B) return 1;
if(arr[1] == C) return 2;
}
int nextl(int i, int A, int B, int C, int D){
vi &p = perms[i];
int l = 100;
if(p[A] > p[D] and p[A] < l) l = p[A];
if(p[B] > p[D] and p[B] < l) l = p[B];
if(p[C] > p[D] and p[C] < l) l = p[C];
if(l == 100) return light(i, A, B, C);
if(l == p[A]) return 0;
if(l == p[B]) return 1;
if(l == p[C]) return 2;
}
int maxh = 0;
int leafcnt = 0;
int cnt;
int build(vi &ps, int n, int h){
if(h > 6) return ps.size() == 0;
maxh = max(h, maxh);
ans[n] = -1;
//if(h < 5) return;
//cout << ps.size() << " " << n << " " << h << endl;
for(int i : ps){
//for(int k : perms[i]) cout << k << " ";
//cout << endl;
}
//cout<<endl;
if(ps.size() == 0) return 1;
if(ps.size() == 1){
leafcnt++;
cnt += h > 6;
ans[n] = ps[0];
return 1;
}
vi bestars; int bestop;
double bestentropy = 0;
// All must be <= |ps|/3
FOR(a, 0, 4) FOR(b, a+1, 5) FOR(c, b+1, 6){
//cerr<<a<<" "<<b<<" "<<c<<endl;
vvi division(3);
for(int i : ps) division[light(i, a, b, c)].pb(i);
if(max(division[0].size(), division[1].size()) <= pows[5-h] and division[2].size() <= pows[5-h]) {
bool done = 1;
FOR(i, 0, 3){
//cout << 0 << endl;
if(!build(division[i], 3*n+i-1, h+1)) {done = false; break;}
}
if(done) {
args[n].pb(a); args[n].pb(b); args[n].pb(c);
op[n] = 0;
return 1;
}
}
}
FOR(a, 0, 4) FOR(b, a+1, 5) FOR(c, b+1, 6){
vvi division(3);
for(int i : ps) division[heavy(i, a, b, c)].pb(i);
if(max(division[0].size(), division[1].size()) <= pows[5-h] and division[2].size() <= pows[5-h]) {
bool done = 1;
FOR(i, 0, 3){
//cout << 1 << endl;
if(!build(division[i], 3*n+i-1, h+1)) {done = false; break;}
}
if(done) {
args[n].pb(a); args[n].pb(b); args[n].pb(c);
op[n] = 1;
return 1;
}
}
}
FOR(a, 0, 4) FOR(b, a+1, 5) FOR(c, b+1, 6){
vvi division(3);
for(int i : ps) division[median(i, a, b, c)].pb(i);
if(max(division[0].size(), division[1].size()) <= pows[5-h] and division[2].size() <= pows[5-h]) {
bool done = 1;
FOR(i, 0, 3){
//cout << 2 << endl;
if(!build(division[i], 3*n+i-1, h+1)) {done = false; break;}
}
if(done) {
args[n].pb(a); args[n].pb(b); args[n].pb(c);
op[n] = 2;
return 1;
}
}
}
FOR(d, 0, 6) FOR(a, 0, 4) FOR(b, a+1, 5) FOR(c, b+1, 6){
//cout<<"lastl test"<<endl;
if(d == a or d == b or d == c) continue;
vvi division(3);
for(int i : ps) division[nextl(i, a, b, c, d)].pb(i);
//cout << division[0].size() << " " << division[1].size() << " " << division[2].size() << endl;
if(max(division[0].size(), division[1].size()) <= pows[5-h] and division[2].size() <= pows[5-h]) {
bool done = 1;
//cout << 3 << endl;
FOR(i, 0, 3){
if(!build(division[i], 3*n+i-1, h+1)) {done = false; break;}
}
if(done) {
args[n].pb(a); args[n].pb(b); args[n].pb(c); args[n].pb(d);
op[n] = 3;
return 1;
}
}
}
return 0;
}
int query(int i, vi arg){
int val = -1;
if(i == 0) val = getLightest(arg[0]+1, arg[1]+1, arg[2]+1)-1;
if(i == 1) val = getHeaviest(arg[0]+1, arg[1]+1, arg[2]+1)-1;
if(i == 2) val = getMedian(arg[0]+1, arg[1]+1, arg[2]+1)-1;
if(i == 3) val = getNextLightest(arg[0]+1, arg[1]+1, arg[2]+1, arg[3]+1)-1;
FOR(i, 0, 3) if(val == arg[i]) return i;
}
int get(int n){
//cout<<n<<endl;
if(ans[n] != -1) return ans[n];
return get( 3*n-1 + query(op[n], args[n]) );
}
void init(INT T) {
op.assign(5000, -1);
args.resize(5000);
ans.assign(5000, -1);
vi p;
FOR(i,0,6) p.pb(i);
do {
perms.pb(p);
} while(next_permutation(p.begin(), p.end()));
//cerr<<perms.size()<<endl;
//for(int w : perms[100]) cout << w << " ";
//cout<<endl;
//cerr<< median(100, 2, 5, 3) << endl;
vi all;
FOR(i, 0, 720)all.pb(i);
build(all, 1, 0);
//cout<<"initialized"<<endl;
//cout<<maxh<<endl;
//cout<<cnt<<endl;
/*cout<<leafcnt<<endl;
FOR(i, 0, 720){
for(int k : perms[i]) cout << k+1 << " ";
cout<<endl;
}*/
}
void orderCoins() {
/* ... */
INT W[] = {1, 2, 3, 4, 5, 6};
int i = get(1);
FOR(j, 0, 6) W[perms[i][j]] = j+1;
answer(W);
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||