| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 68664 | FLDutchman | 저울 (IOI15_scales) | C++14 | 35 ms | 992 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;
void build(vi &ps, int n, int h){
maxh = max(h, maxh);
//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;
if(ps.size() == 1){
leafcnt++;
ans[n] = ps[0];
return;
}
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){
vi division(3);
for(int i : ps) division[light(i, a, b, c)]++;
//cerr << max(division[0].size(), max(division[1].size(), division[2].size())) << endl;
double entr = 0;
FOR(i, 0, 3){
double p0 = (double)division[i]/(double)ps.size();
if(p0!=0)entr -= p0 * log(p0);
}
//double entr = max(division[0], max(division[1], division[2]));
if(entr > bestentropy) {
bestars.clear();
bestars.pb(a); bestars.pb(b); bestars.pb(c);
bestop = 0;
bestentropy = entr;
}
}
FOR(a, 0, 4) FOR(b, a+1, 5) FOR(c, b+1, 6){
vi division(3);
for(int i : ps) division[heavy(i, a, b, c)]++;
//cerr << max(division[0].size(), max(division[1].size(), division[2].size())) << endl;
double entr = 0;
FOR(i, 0, 3){
double p0 = (double)division[i]/(double)ps.size();
if(p0!=0)entr -= p0 * log(p0);
}
//double entr = max(division[0], max(division[1], division[2]));
if(entr > bestentropy) {
bestars.clear();
bestars.pb(a); bestars.pb(b); bestars.pb(c);
bestop = 1;
bestentropy = entr;
}
}
FOR(a, 0, 4) FOR(b, a+1, 5) FOR(c, b+1, 6){
vi division(3);
for(int i : ps) division[median(i, a, b, c)]++;
//cerr << max(division[0].size(), max(division[1].size(), division[2].size())) << endl;
double entr = 0;
FOR(i, 0, 3){
double p0 = (double)division[i]/(double)ps.size();
if(p0!=0)entr -= p0 * log(p0);
}
//double entr = max(division[0], max(division[1], division[2]));
if(entr > bestentropy) {
bestars.clear();
bestars.pb(a); bestars.pb(b); bestars.pb(c);
bestop = 2;
bestentropy = entr;
}
}
FOR(d, 0, 6) FOR(a, 0, 4) FOR(b, a+1, 5) FOR(c, b+1, 6){
if(d != a and d != b and d != c);
vi division(3, 0);
for(int i : ps) division[nextl(i, a, b, c, d)]++;
//cerr << max(division[0].size(), max(division[1].size(), division[2].size())) << endl;
double entr = 0;
FOR(i, 0, 3){
double p0 = (double)division[i]/(double)ps.size();
if(p0!=0)entr -= p0 * log(p0);
}
//double entr = max(division[0], max(division[1], division[2]));
if(entr > bestentropy) {
bestars.clear();
bestars.pb(a); bestars.pb(b); bestars.pb(c); bestars.pb(d);
bestop = 3;
bestentropy = entr;
}
}
//cout << D[0].size() << " " <<D[1].size()<<" "<<D[2].size()<<endl;
args[n] = bestars;
op[n] = bestop;
vvi D(3);
if(bestop == 0) for(int i : ps) D[light(i, bestars[0], bestars[1], bestars[2])].pb(i);
if(bestop == 1) for(int i : ps) D[heavy(i, bestars[0], bestars[1], bestars[2])].pb(i);
if(bestop == 2) for(int i : ps) D[median(i, bestars[0], bestars[1], bestars[2])].pb(i);
if(bestop == 3) for(int i : ps) D[nextl(i, bestars[0], bestars[1], bestars[2], bestars[3])].pb(i);
FOR(i, 0, 3){
build(D[i], 3*n+i-1, h+1);
}
}
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<<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... | ||||