Submission #237934

#	Time	Username	Problem	Language	Result	Execution time	Memory
237934		crossing0ver	저울 (IOI15_scales)	C++17	0 / 100	24 ms	768 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.

scales

#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};
	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++;
	 }
	 else if (P[1] != -1 && P[2] != -1) {
	 	if (f && P[1] > P[2]) continue;
	 	if (P[1] < P[2]) s1++;
	 	else s2++;
	 }
	 else if (P[0] != -1 && P[1] != -1) {
	 	if (P[0] < P[1]) s2++;
	 	else s1++;
	 }
	 else if (P[0] != -1 && P[2] != -1) {
	 	if (P[0] < P[2]) s1++;
	 	else s2++;
	 }
	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;
			 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);
	 }
	 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);
	 }
	 if (o)
	 h.push_back(g);
}}     if (o)
	 Left = h;
	int cnt = s1 + s2;
	for (int i = 1; i <= 6; i++) process(i);
	return max(s1,s2);
}
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 : Left[0]) W[i] = i;
	 //	answer(W);
	 for (int i =0 ; i <6 ; i++) cout << W[i] <<' ';
	 	return;
	 }
    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];
	
}       */

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:27:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^
scales.cpp: In function 'int calculate()':
scales.cpp:44:13: warning: declaration of 'g' shadows a global declaration [-Wshadow]
   for (auto g:Left) {
             ^
scales.cpp:7:13: note: shadowed declaration is here
 vector<int> g,to_ask;
             ^
scales.cpp: In function 'void lower(int, int)':
scales.cpp:73:11: warning: declaration of 'int j' shadows a parameter [-Wshadow]
  for (int j:b) cmp[i][j] = -1, cmp[j][i] = 1;
           ^
scales.cpp:54:22: note: shadowed declaration is here
 void lower(int k,int j) {
                      ^
scales.cpp: In function 'void GO(int, int)':
scales.cpp:104:11: warning: declaration of 'int j' shadows a parameter [-Wshadow]
  for (int j:b) Rcmp[i][j] = -1, Rcmp[j][i] = 1;
           ^
scales.cpp:82:19: note: shadowed declaration is here
 void GO(int k,int j) {
                   ^
scales.cpp:106:11: warning: declaration of 'int j' shadows a parameter [-Wshadow]
  for (int j = 1; j <= 6 ;j++)
           ^
scales.cpp:82:19: note: shadowed declaration is here
 void GO(int k,int j) {
                   ^
scales.cpp: In function 'int calculate_mid(int, int, int, bool)':
scales.cpp:153:12: warning: declaration of 'g' shadows a global declaration [-Wshadow]
  for (auto g:Left) {
            ^
scales.cpp:7:13: note: shadowed declaration is here
 vector<int> g,to_ask;
             ^
scales.cpp:155:9: warning: unused variable 'flag' [-Wunused-variable]
    bool flag = 1;
         ^~~~
scales.cpp:228:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt = s1 + s2;
      ^~~
scales.cpp: In function 'void orderCoins()':
scales.cpp:380:23: warning: declaration of 'g' shadows a global declaration [-Wshadow]
  vector<vector<int> > g;
                       ^
scales.cpp:7:13: note: shadowed declaration is here
 vector<int> g,to_ask;
             ^
scales.cpp:381:12: warning: declaration of 'v' shadows a previous local [-Wshadow]
  for (auto v:Left) {
            ^
scales.cpp:352:17: note: shadowed declaration is here
     vector<int> v = to_ask;
                 ^
scales.cpp:392:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0 ; i <  Left[0].size(); i++) W[i] =Left[0][i];
                     ~~^~~~~~~~~~~~~~~~~

Subtask 10 / 100

#	Verdict	Execution time	Memory	Grader output
Fetching results...