Submission #127375

#	Time	Username	Problem	Language	Result	Execution time	Memory
127375		ekrem	Scales (IOI15_scales)	C++98	77.68 / 100	403 ms	504 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define N 1005
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;
typedef vector < int > vi;

int n, say, amk, u[N], uu[N];
vector < vi > a;
vi x, ans;
pair < ii , int > mx, kac;

void dfs(int ind){
	if(ind == 6){
		a.pb(x);
		say++;
		// if(rand()%100 == 0)for(int i = 1; i <= 6; i++)cout << x[i] << " ";cout << endl;
		return;
	}
	for(int i = 1; i <= 6; i++)
		if(!uu[i]){
			uu[i]++;
			x.pb(i);
			dfs(ind + 1);
			x.pop_back();
			uu[i]--;
		}
}

int getL(int i, int bir, int iki, int uc, int ans, int d){
	if(a[i][bir] >= a[i][ans] and a[i][iki] >= a[i][ans] and a[i][uc] >= a[i][ans])
		return 0;
	u[i] += d;
	return 1;
}

int getH(int i, int bir, int iki, int uc, int ans, int d){
	if(a[i][bir] <= a[i][ans] and a[i][iki] <= a[i][ans] and a[i][uc] <= a[i][ans])
		return 0;
	u[i] += d;
	return 1;
}

int getM(int i, int bir, int iki, int uc, int ans, int d){
	int buy = 0, kuc = 0;
	if(a[i][bir] <= a[i][ans])
		kuc++;
	else
		buy++;
	if(a[i][iki] <= a[i][ans])
		kuc++;
	else
		buy++;
	if(a[i][uc] <= a[i][ans])
		kuc++;
	else
		buy++;
	if(kuc == 2 and buy == 1)
		return 0;
	u[i] += d;
	return 1;
}

int getN(int i, int bir, int iki, int uc, int dor, int ans, int d){
	ii mn = mp(inf, inf);
	if(a[i][bir] > a[i][dor])mn = min(mn, mp(a[i][bir], bir));
	if(a[i][iki] > a[i][dor])mn = min(mn, mp(a[i][iki], iki));
	if(a[i][uc] > a[i][dor])mn = min(mn, mp(a[i][uc], uc));
	if(mn.st == inf){
		mn = min(mn, mp(a[i][bir], bir));
		mn = min(mn, mp(a[i][iki], iki));
		mn = min(mn, mp(a[i][uc], uc));
	}
	if(mn.nd == ans)
		return 0;
	u[i] += d;
	return 1;
}

int sorr(int bir, int iki, int uc, int dor, int ans, int d){
	int say = 0;
	for(int i = 1; i <= 720; i++){
		if(u[i])
			continue;
		// if(bir == 1 and iki == 2 and uc == 3 and dor == -1)
		// 	cout << ans << " " << say << " " << d << endl;
		if(dor == -2)
			say += getL(i, bir, iki, uc, ans, d);
		else if(dor == -1)
			say += getM(i, bir, iki, uc, ans, d);
		else if(dor == 0)
			say += getH(i, bir, iki, uc, ans, d);
		else
			say += getN(i, bir, iki, uc, dor, ans, d);
	}
	return say;
}

void sor(int ind){
	if(ind == 3){
		for(int i = -2; i <= 6; i++)
			if(!uu[i]){
				x.pb(i);

				kac.st.st = sorr(x[1], x[2], x[3], x[4], x[1], 0);
				kac.st.nd = sorr(x[1], x[2], x[3], x[4], x[2], 0);
				kac.nd = sorr(x[1], x[2], x[3], x[4], x[3], 0);
				if(kac.nd < kac.st.nd)
					swap(kac.nd, kac.st.nd);
				if(kac.st.nd < kac.st.st)
					swap(kac.st.nd, kac.st.st);
				if(kac.nd < kac.st.nd)
					swap(kac.nd, kac.st.nd);
				if(kac >= mx){
					mx = kac;
					ans = x;
				}
				x.pop_back();
			}
		return;
	}
	for(int i = 1; i <= 6; i++)
		if(!uu[i]){
			uu[i]++;
			x.pb(i);
			sor(ind + 1);
			x.pop_back();
			uu[i]--;
		}
}


void init(int T){
}

void orderCoins(){

	a.clear();x.clear();ans.clear();
	memset(u, 0, sizeof u);
	memset(uu, 0, sizeof uu);
	say = 0;

	x.pb(0);
	a.pb(x);
	dfs(0);
	// cout << a.size() << endl;
	int W[] = {1, 2, 3, 4, 5, 6};
	// cout << getLightest(1, 2, 3) << endl;
	// cout << getHeaviest(1, 2, 3) << endl;
	// cout << getMedian(1, 2, 3) << endl;

	while(say > 1){
		// cout << say << endl;
		// amk++;if(amk >= 100)assert(0);
		mx = mp(mp(-1, -1), -1);
		if(say != 720)
			sor(0);
		else{ans.resize(6);
		ans[1] = 1;
		ans[2] = 2;
		ans[3] = 6;
		ans[4] = -1;}
		// cout << mx << endl;
		// cout << ans[1] << " " << ans[2] << " " << ans[3] << " " << ans[4] << " -> ";
		
		int cvp = 0;
		if(ans[4] == -2)
			cvp = getLightest(ans[1], ans[2], ans[3]);
		else if(ans[4] == -1)
			cvp = getMedian(ans[1], ans[2], ans[3]);
		else if(ans[4] == 0)
			cvp = getHeaviest(ans[1], ans[2], ans[3]);
		else
			cvp = getNextLightest(ans[1], ans[2], ans[3], ans[4]);
		say -= sorr(ans[1], ans[2], ans[3], ans[4], cvp, 1);

	}
	for(int i = 1; i <= 720; i++){
		if(u[i])continue;
		for(int j = 1; j <= 6; j++)
			W[a[i][j] - 1] = j;
	}
	// cout << say << endl;

	answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'int getL(int, int, int, int, int, int)':
scales.cpp:42:57: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
 int getL(int i, int bir, int iki, int uc, int ans, int d){
                                                         ^
scales.cpp:22:7: note: shadowed declaration is here
 vi x, ans;
       ^~~
scales.cpp: In function 'int getH(int, int, int, int, int, int)':
scales.cpp:49:57: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
 int getH(int i, int bir, int iki, int uc, int ans, int d){
                                                         ^
scales.cpp:22:7: note: shadowed declaration is here
 vi x, ans;
       ^~~
scales.cpp: In function 'int getM(int, int, int, int, int, int)':
scales.cpp:56:57: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
 int getM(int i, int bir, int iki, int uc, int ans, int d){
                                                         ^
scales.cpp:22:7: note: shadowed declaration is here
 vi x, ans;
       ^~~
scales.cpp: In function 'int getN(int, int, int, int, int, int, int)':
scales.cpp:76:66: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
 int getN(int i, int bir, int iki, int uc, int dor, int ans, int d){
                                                                  ^
scales.cpp:22:7: note: shadowed declaration is here
 vi x, ans;
       ^~~
scales.cpp: In function 'int sorr(int, int, int, int, int, int)':
scales.cpp:92:59: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
 int sorr(int bir, int iki, int uc, int dor, int ans, int d){
                                                           ^
scales.cpp:22:7: note: shadowed declaration is here
 vi x, ans;
       ^~~
scales.cpp:93:6: warning: declaration of 'say' shadows a global declaration [-Wshadow]
  int say = 0;
      ^~~
scales.cpp:20:8: note: shadowed declaration is here
 int n, say, amk, u[N], uu[N];
        ^~~
scales.cpp: In function 'void init(int)':
scales.cpp:145:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T){
               ^

• Subtask 1: 77.678571 / 100