Submission #237994

#	Time	Username	Problem	Language	Result	Execution time	Memory
237994		crossing0ver	Scales (IOI15_scales)	C++17	74.11 / 100	948 ms	516 KiB

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 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;
	 } 
	}
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:26:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^
scales.cpp: In function 'int calc(std::vector<int>, int, int, int)':
scales.cpp:55: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: In function 'void cnt_min()':
scales.cpp:83:17: warning: declaration of 'g' shadows a global declaration [-Wshadow]
     vector<int> g;
                 ^
scales.cpp:7:13: note: shadowed declaration is here
 vector<int> g,to_ask;
             ^
scales.cpp: In function 'void orderCoins()':
scales.cpp:130:16: warning: declaration of 'g' shadows a global declaration [-Wshadow]
    vector<int> g;
                ^
scales.cpp:7:13: note: shadowed declaration is here
 vector<int> g,to_ask;
             ^
scales.cpp:138: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];
                     ~~^~~~~~~~~~~~~~~~~
scales.cpp:115:7: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   calc(v,p,0,0); 
   ~~~~^~~~~~~~~

• Subtask 1: 74.107143 / 100