| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 237993 | crossing0ver | 저울 (IOI15_scales) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#define ll long long
#include "scales.h"
using namespace std;
vector<vector<int> > all,sall;
vector<vector<int> > Left1,Left;
vector<int> g,to_ask;
bool vis[7];
int oper,X[7];
void G(int c) {
if (c == 6) {
Left1.push_back(g);
return;
}
for (int i = 1; i <= 6; i++) {
if (!vis[i]) {
g.push_back(i);
vis[i] = 1;
G(c+1);
vis[i] = 0;
g.pop_back();
}
}
}
void init(int T) {
for (int i = 1; i<=6;i++)
for (int j = i + 1; j <= 6; j++)
for (int k = j+1;k <=6;k++) {
all.push_back({i,j,k});
for (int f = 1; f <= 6; f++) {
if (f != j && f != i && f != k)
sall.push_back({i,j,k,f});
}
}
G(0);
Left = Left1;
}
void minimize(int &total_ans,int &c,int type,vector<int> v) {
if (total_ans > c) {
total_ans = c;
to_ask = v;
oper = type;
}
}
vector<vector<int> > F;
bool flag;
int calc(vector<int> v,int p = 0,int type = 0 ,int d = 0) {
F.clear();
int a[7] = {0},cnt = 0;
vector<int> h;
for (int i : v) if (i != v[p]) h.push_back(i);
for (auto g : Left) {
for (int i = 0; i < 6; i++) a[ g[i] ] = i;
if (type == 0 && a[ v[p] ] < min( a[ h[0] ], a[ h[1] ]) ) {cnt++; if (flag) F.push_back(g);}
if (type == 1 && a[ v[p] ] > max( a[ h[0] ], a[ h[1] ])) {cnt++; if (flag) F.push_back(g);}
if (type == 2 && a[ v[p] ] < max( a[ h[0] ], a[ h[1] ]) && a[ v[p] ] > min( a[ h[0] ], a[ h[1] ]) ) {cnt++; if (flag) F.push_back(g);}
if (type == 3) {
vector<pair<int,int> > c;
c.emplace_back ( a[ v[p] ],v[p]);
c.emplace_back ( a[ h[0] ], h[0]);
c.emplace_back ( a[ h[1] ], h[1]);
sort (c.begin(),c.end());
if ( a[d] > a[ c.back().second ]) {
if (c[0].second == v[p]) {cnt++; if (flag) F.push_back(g);}
}
else {
auto pos = lower_bound(c.begin(),c.end(), make_pair(a[d],0));
if ( (*pos).second == v[p]) {cnt++; if (flag) F.push_back(g);}
}
}
}
if (flag) Left = F;
return cnt;
}
void cnt_min(){
int total_ans = 10000;
for (auto v:sall) {
int d = v[3];
vector<int> g;
int c = 0;
for (int i =0 ; i < 3; i++) g.push_back(v[i]);
for (int i = 0; i < 3; i++)
c = max(c,calc(g,i,3,d));
minimize(total_ans,c,3,v);
}
for (auto v : all) {
for (int type = 2; type >= 0; type--) {
int c = 0;
for (int i = 0; i < 3; i++)
c = max(c,calc(v,i,type,0));
minimize(total_ans,c,type,v);
}
}
}
void orderCoins() {
Left = Left1;
int r = 10;
while(r--) {
cnt_min();
vector<int> v = to_ask;
int p;
flag = 1;
if (oper == 0) {
int a = getLightest(v[0],v[1],v[2]);
for (int i = 0; i < 3; i++) if (a == v[i]) p = i;
calc(v,p,0,0);
}
if (oper == 1) {
int a = getHeaviest(v[0],v[1],v[2]);
for (int i = 0; i < 3; i++) if (a == v[i]) p = i;
calc(v,p,1,0);
}
if (oper == 2) {
int a = getMedian(v[0],v[1],v[2]);
for (int i = 0; i < 3; i++) if (a == v[i]) p = i;
calc(v,p,2,0);
}
if (oper == 3) {
int a = getNextLightest(v[0], v[1], v[2], v[3]);
int d = v[3];
vector<int> g;
for (int i =0 ; i < 3; i++) g.push_back(v[i]);
for (int i = 0; i < 3; i++) if (a == v[i]) p = i;
calc(g,p,3,d);
}
flag = 0;
if (Left.size() == 1){
int W[6];
for (int i = 0 ; i < Left[0].size(); i++) W[i] =Left[0][i];
answer(W);
return;
}
}
}