| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 237983 | crossing0ver | 저울 (IOI15_scales) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#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 cmp[7][7],lets[7][7] , Rcmp[7][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 : all) {
for (int type = 0; type < 3; 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);
}
}
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);
}
}
// 0 getLightest(A, B, C) 1 getHeaviest(A, B, C) ,2 getMedian(A, B, C) 3 getNextLightest(A, B, C, D)
/*
int getLightest(int a,int b,int c){
vector<int> v= {a,b,c};
if (X[a] < X[b] && X[a] < X[c]) return a;
if (X[b] < X[c]) return b;
return c;
}
int getHeaviest(int a,int b,int c){
vector<int> v= {a,b,c};
if (X[a] > X[b] && X[a] > X[c]) return a;
if (X[b] > X[c]) return b;
return c;
}
int getMedian(int a,int b,int c){
vector<int> v= {a,b,c};
if (X[a] > X[b] && X[a] < X[c]) return a;
if (X[a] > X[c] && X[a] < X[b]) return a;
if (X[b] > X[a] && X[b] < X[c]) return b;
if (X[b] < X[a] && X[b] > X[c]) return b;
return c;
}
int getNextLightest(int a,int b,int c,int d) {
vector<pair<int,int> > v;
v.push_back({X[a],a});
v.push_back({X[b],b});
v.push_back({X[c],c});
v.push_back({X[d],d});
sort(v.begin(),v.end());
if (v.back().second == d) return v[0].second;
for (int i = 0; i <= 3; i++) {
if (v[i].second == d) return v[i+1].second;
}
} */
void orderCoins() {
Left = Left1;
int r = 10;
while(r--) {
cnt_min();
vector<int> v = to_ask;
// for(int i : v) cout << i <<' ';
// cout << endl;
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);
}
if (Left.size() == 1){
int W[6];
for (int i = 0 ; i < Left[0].size(); i++) W[i] =Left[0][i];
// for (int i : Left[0]) cout << i << 's';
answer(w);
return;
}
flag = 0;
}
} /*
int main(){
srand(time(NULL));
int Y[7];
for (int i = 1; i <= 6; i++) Y[i] = i;
random_shuffle(Y+1,Y+7);
for (int i = 1; i <= 6; i++) cout << Y[i] <<' ',X[Y[i]] = i;
cout << endl;
init(5);
orderCoins(); exit(0);
cout << endl << Left.size()<<'\n';
int s =0;
// cout << Rcmp[4][3] << ' '<<Rcmp[3][6];
//cnt_min();
//for (int i :to_ask) cout << i <<' ';
exit(0);
// int a = getMedian(1,4,6);
// cout << Rcmp[1][4] <<'\n';
// for (int i = 1; i <= 6; i++)
// for (int j = i+1; j <= 6 ;j++)
// if(Rcmp[i][j] ==0 ) cout << i <<' '<<j;
// cout << s <<" "<<Rcmp[1][6];
} */