| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 237904 | crossing0ver | Scales (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;
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 (!Rcmp[k][i] && cmp[j][i] == -1) {
cmp[k][i] = -1;
cmp[i][k] = 1;
}
if (!Rcmp[j][i] && cmp[k][j] == 1) {
cmp[j][i] = 1;
cmp[i][j] = -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;
}
}
}
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 = 0;
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;
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]);
}
minimize(total_ans,c,0,v);
c = 0;
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;
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]);
}
minimize(total_ans,c,1,v);
c = 0; }
/*
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) || (cmp[ans][h[0]] == 1 && cmp[ans][h[1]] == 1) ) continue;
if (cmp[h[0]][h[1]] != 0) {
if (cmp[h[0]][h[1]] == 1)
lower(ans,h[0]);
else lower(ans,h[1]);
c = max(c,calculate());
}
else {
if (cmp[ans][h[0]] != 0) {
if (cmp[ans][h[0]] == -1)
lower(h[1],ans);
else lower(ans,h[1]);
c = max(c,calculate());
}
else if (cmp[ans][h[1]] != 0){
if (cmp[ans][h[1]] == -1)
lower(h[0],ans);
else lower(ans,h[0]);
c = max(c,calculate());
}
else {
lower(ans,h[0]);
lower(h[1],ans);
c = max(c,calculate());
process(ans);
process(h[0]);
process(h[1]);
lower(ans,h[1]);
lower(h[0],ans);
c = max(c,calculate());
}
}
process(ans);
process(h[0]);
process(h[1]);
}
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)
void orderCoins() {
Left = Left1;
/* ... */
while(true) {
cnt_min();
vector<int> v = to_ask;
int a;
if (oper == 0) {
a = getLightest(v[0],v[1],v[2]);
for (int i:v) if (a != i) GO(a,i);
}
if (oper == 1) {
a = getHeaviest(v[0],v[1],v[2]);
for (int i:v) if (a != i) GO(i,a);
}
if (oper == 2) {
a = greatest(v[0],v[1],v[2]);
}
if (oper == 0) {
a = getMedian(v[0],v[1],v[2]);
}
for (int i = 1; i <= 6; i++) process(i);
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 ( cmp[v[i]][v[j]] == 1 ) flag = 0;
}
if (flag) g.push_back(v);
}
Left = g;
if (Left.size() == 1){
int W[6];
for (int i : Left[0]) W[i] = i;
answer(W);
return;
}
}
}
int main(){
init(5);
cnt_min();
}