| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 237941 | crossing0ver | 저울 (IOI15_scales) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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,j,f});
}
}
G(0);
Left = Left1;
//cout << all.size() << ' ' << Left.size();
}
int calculate() {
int cnt = 0;
for (auto g:Left) {
bool flag = 1;
for (int i = 0; i < 6; i++)
for (int j = i+1; j < 6; j++) {
if ( cmp[g[i]][g[j]] == 1 ) flag = 0;
}
if (flag) cnt++;
}
return cnt;
}
void lower(int k,int j) {
cmp[k][j] = -1;
cmp[j][k] = 1;
for (int i = 1; i <= 6 ;i++) {
if (cmp[j][i] == -1) {
cmp[k][i] = -1;
cmp[i][k] = 1;
}
if (cmp[k][j] == 1) {
cmp[j][i] = 1;
cmp[i][j] = -1;
}
}
vector<int> a,b;
for (int s = 1; s <= 6; s++) {
if (cmp[k][s] == 1) a.push_back(s);
if (cmp[j][s] == -1) b.push_back(s);
}
for (int i:a)
for (int j:b) cmp[i][j] = -1, cmp[j][i] = 1;
}
void process(int k) {
for (int i = 1; i <= 6; i++) {
cmp[k][i] = Rcmp[k][i];
cmp[i][k] = Rcmp[i][k];
}
}
void GO(int k,int j) {
Rcmp[k][j] = -1;
Rcmp[j][k] = 1;
for (int i = 1; i <= 6 ;i++) {
if (Rcmp[j][i] == -1) {
Rcmp[k][i] = -1;
Rcmp[i][k] = 1;
}
if (Rcmp[k][j] == 1) {
Rcmp[j][i] = 1;
Rcmp[i][j] = -1;
}
}
vector<int> a,b;
for (int s = 1; s <= 6; s++) {
if (Rcmp[k][s] == 1) a.push_back(s);
if (Rcmp[j][s] == -1) b.push_back(s);
}
a.push_back(k);
b.push_back(j);
for (int i:a)
for (int j:b) Rcmp[i][j] = -1, Rcmp[j][i] = 1;
for (int i = 1; i <= 6 ;i++)
for (int j = 1; j <= 6 ;j++)
cmp[i][j] = Rcmp[i][j];
}
int calculate_mid(int a = 1,int b = 1,int c = 1,bool o = 0) {
int P[] = {-1,-1,-1},cnt = 0;
int s1 = 0, s2 = 0;
if (Rcmp[b][c] == 1) swap(b,c);
else if (Rcmp[a][c] == 1) swap(b,c);
int f = 0;
if (Rcmp[a][b] == 1 && o) {
Rcmp[a][c] = -1;
Rcmp[c][a] = 1;
GO(a,c);
}
else
if (Rcmp[a][c] == 1 && o) {
Rcmp[a][b] = -1;
Rcmp[b][a] = 1;
GO(a,b);
}
else
if (Rcmp[a][b] == -1 && o) {
GO(c,a);
GO(c,b);
}
else
if (Rcmp[a][c] == -1 && o) {
GO(a,b);
GO(c,b);
}
if (Rcmp[b][c] == 1 && o) {
GO(c,a);
GO(a,b);
swap(b,c);
}
if (Rcmp[b][c] == -1 && o){
GO(b,a);
GO(a,c);
}
if (Rcmp[b][c] == -1) f = 1;
if (Rcmp[b][c] == 1) {swap(b,c); f = 1;}
if (Rcmp[a][b] == 1) { f = 1;}
if (Rcmp[a][b] == -1) { f = 1;swap(b,c);}
if (Rcmp[a][c] == -1) { f = 1;}
if (Rcmp[a][c] == 1) { f = 1;swap(b,c);}
vector<vector<int> > h;
for (auto g:Left) {
P[0] = P[1] = P[2] = -1;
bool flag = 1;
for (int i = 0; i < 6; i++) {
if (g[i] == a) P[0] = i;
if (g[i] == b) P[1] = i;
if (g[i] == c) P[2] = i;
}
if (P[0] != -1 && P[1] != -1 && P[2] != -1) {
if (f && P[1] > P[2]) continue;
if ( ( P[0] > max(P[1],P[2])) || P[0] < min(P[1],P[2])) continue;
if (P[1] < P[2]) s1++;
else s2++;
cnt++;
}
else if (P[1] != -1 && P[2] != -1) {
if (f && P[1] > P[2]) continue;
if (P[1] < P[2]) s1++;
else s2++;
cnt++;
}
else if (P[0] != -1 && P[1] != -1) {
if (P[0] < P[1]) s2++;
else s1++;
cnt++;
}
else if (P[0] != -1 && P[2] != -1) {
if (P[0] < P[2]) s1++;
else s2++;
cnt++;
}
else {
vector<int> v = g;
if (P[0] != -1) {
bool flag1 = 1,flag2= 1;
for (int i = 0; i < 6; i++) {
if (v[i] != a) {
if (Rcmp[b][v[i]] == 1 && i > P[0])
flag1 = 0;
if (Rcmp[c][v[i]] == -1 && i < P[0])
flag2 = 0;
}
}
if (f == 1 && (flag1 == 0 || flag2 == 0)) continue;
cnt++;
s1+=(flag1 != 0);
s2+=(flag2 != 0);
}
else if (P[1]!=-1) {
bool flag1 = 1,flag2= 1;
for (int i = 0; i < 6; i++) {
if (v[i] != b) {
if (Rcmp[a][v[i]] == -1 && i < P[1])
flag1 = 0;
if (Rcmp[a][v[i]] == 1 && i > P[1])
flag2 = 0;
}
}
if (f == 1 && (flag1 == 0 || flag2 ==0))continue;
s1+=(flag1 != 0);
s2+=(flag2 != 0);
cnt++;
}
else if (P[2] != -1) {
bool flag1 = 1,flag2= 1;
for (int i = 0; i < 6; i++) {
if (v[i] != c) {
if (Rcmp[a][v[i]] == 1 && i > P[2])
flag2 = 0;
if (Rcmp[a][v[i]] == -1 && i < P[2])
flag1 = 0;
}
}
if (f == 1 && (flag1 == 0 || flag2 == 0))continue;
s1+=(flag1 != 0);
s2+=(flag2 != 0);
cnt++;
}
if (o)
h.push_back(g);
}} if (o)
Left = h;
for (int i = 1; i <= 6; i++) process(i);
return cnt;
}
void minimize(int &total_ans,int &c,int type,vector<int> v) {
if (total_ans > c) {
total_ans = c;
to_ask = v;
oper = type;
}
}
void cnt_min(){
int total_ans = 10000;
for (auto v : all) {
int a[3];
memset(a,0,sizeof a);
vector<int> h;
int c = -1;
for (int ans : v) {
h = v;
h.erase(find(h.begin(),h.end(),ans));
process(ans);
process(h[0]);
process(h[1]);
if (cmp[ans][h[0]] == 1 || cmp[ans][h[1]] == 1) continue;
if (Rcmp[ans][h[0]] == -1 && Rcmp[ans][h[1]] == -1 ) continue;
lower(ans,h[0]);
lower(ans,h[1]);
if (cmp[h[0]][h[1]] == 0) {
lower(h[0],h[1]);
c = max( calculate(),c);
process(h[0]);
process(h[1]);
lower(ans,h[0]);
lower(ans,h[1]);
lower(h[1],h[0]);
c = max( calculate(),c);
}
else c = max(c,calculate());
process(ans);
process(h[0]);
process(h[1]);
}
if (c != -1)
minimize(total_ans,c,0,v);
c = -1;
for (int ans : v) {
h = v;
h.erase(find(h.begin(),h.end(),ans));
process(ans);
process(h[0]);
process(h[1]);
if (cmp[ans][h[0]] == -1 || cmp[ans][h[1]] == -1) continue;
if (Rcmp[ans][h[0]] == 1 && Rcmp[ans][h[1]] == 1) continue;
lower(h[0],ans);
lower(h[1],ans);
if (cmp[h[0]][h[1]] == 0) {
lower(h[0],h[1]);
c = max( calculate(),c);
process(h[0]);
process(h[1]);
lower(h[0],ans);
lower(h[1],ans);
lower(h[1],h[0]);
c = max( calculate(),c);
}
else c = max(c,calculate());
process(ans);
process(h[0]);
process(h[1]);
}
if (c != -1)
minimize(total_ans,c,1,v);
c = 0;
for (int ans : v) {
h = v;
h.erase(find(h.begin(),h.end(),ans));
if ((Rcmp[ans][h[0]] == -1 && Rcmp[ans][h[1]] == -1 ) || (Rcmp[ans][h[0]] == 1 && Rcmp[ans][h[1]] == 1) ) continue;
c = max(c,calculate_mid(ans,h[0],h[1],0));
}
minimize(total_ans,c,2,v);
c = 0;
}
/* for (auto v:sall) {
vector<int> h;
}*/
}
// 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;
} */
void orderCoins() {
Left = Left1;
/* ... */
while(true) {
cnt_min();
vector<int> v = to_ask;
if (Left.size() == 1){
int W[6];
for (int i = 0 ; i < Left[0].size(); i++) W[i] =Left[0][i];
// answer(W);
// for (int i =0 ; i <6 ; i++) cout << W[i] <<' ';
answer(W);
}
int a;
if (oper == 0) {
a = getLightest(v[0],v[1],v[2]);
for (int i:v) if (a != i) Rcmp[a][i] = -1,Rcmp[i][a] = 1,GO(a,i);
}
if (oper == 1) {
a = getHeaviest(v[0],v[1],v[2]);
for (int i:v) if (a != i) Rcmp[a][i] = 1,Rcmp[i][a] = -1,GO(i,a);
}
if (oper == 2) {
a = getMedian(v[0],v[1],v[2]);
vector<int> h = v;
h.erase(find(h.begin(),h.end(),a));
calculate_mid(a,h[0],h[1],1);
}
// if (oper == 0) {
/// a = getMedian(v[0],v[1],v[2]);
// }
for (int i = 1; i <= 6; i++) process(i);
// if (oper != 2) {
vector<vector<int> > g;
for (auto v:Left) {
bool flag = 1;
for (int i = 0; i < 6; i++)
for (int j = i+1; j < 6; j++) {
if ( Rcmp[v[i]][v[j]] == 1) flag = 0;
}
if (flag) g.push_back(v);
}
Left = g; //cout << Left.size()<<' ';
if (Left.size() == 1){
int W[6];
for (int i = 0 ; i < Left[0].size(); i++) W[i] =Left[0][i];
// answer(W);
// for (int i =0 ; i <6 ; i++) cout << W[i] <<' ';
answer(W);
}
}
} /*
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();
cout << endl << Left.size()<<'\n';
for (auto v:Left) {
for (int i:v) cout << i <<' ';
cout <<endl;
}
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];
} */