Submission #792141

#	Time	Username	Problem	Language	Result	Execution time	Memory
792141		NothingXD	Scales (IOI15_scales)	C++17	100 / 100	391 ms	572 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

vector<vector<int>> perm;
vector<vector<int>> query;

void init(int T) {
	for (int d = 0; d < 6; d++){
		for (int i = 0; i < 6; i++){
			for (int j = i+1; j < 6; j++){
				for (int k = j+1; k < 6; k++){
					if (i == d || j == d || k == d) continue;
					query.push_back({i, j, k, d});
				}
			}
		}
	}

	for (auto x: {-2, -3, -1}){
		for (int i = 0; i < 6; i++){
			for (int j = i+1; j < 6; j++){
				for (int k = j+1; k < 6; k++){
					query.push_back({i, j, k, x});
				}
			}
		}
	}
}

int get(vector<int> a, int x, int y, int z, int idx){
	if (perm.size() == 6) debug(x, y, z, idx);
	vector<int> tmp = {a[x], a[y], a[z]};
	sort(all(tmp));
	if (tmp[idx] == a[x]) return 0;
	if (tmp[idx] == a[y]) return 1;
	if (tmp[idx] == a[z]) return 2;
}

int getnext(vector<int> a, int x, int y, int z, int d){
	vector<int> tmp = {a[x], a[y], a[z]};
	sort(all(tmp));
	int idx = 0;
	for (int i = 0; i < 3; i++){
		if (tmp[i] > a[d]){
			idx = i;
			break;
		}
	}
	if (tmp[idx] == a[x]) return 0;
	if (tmp[idx] == a[y]) return 1;
	if (tmp[idx] == a[z]) return 2;
}

void solve(){
	//debug(perm.size());
	if (perm.size() == 6){
		for (auto x: perm){
			for (auto y: x) cerr << y << ' ';
			cerr << endl;
		}
	}
	if (perm.size() == 1) return;
	int mx = perm.size() + 1;
	vector<vector<int>> ans[3];
	vector<int> q;
	for (auto x: query){
		vector<vector<int>> res[3];
		for (auto y: perm){
			if (x[3] >= 0){
				int tmp = getnext(y, x[0], x[1], x[2], x[3]);
				res[tmp].push_back(y);
			}
			else{
				int tmp = get(y, x[0], x[1], x[2], -x[3] - 1);
				res[tmp].push_back(y);
			}
		}
		if (perm.size() == 6 && x[3] < 0){
		//	debug(x[0], x[1], x[2], x[3], res[0].size(), res[1].size(), res[2].size());
		}
		int tmp = max({res[0].size(), res[1].size(), res[2].size()});
		if (tmp < mx){
			mx = tmp;
			for (int i = 0; i < 3; i++){
				ans[i] = res[i];
			}
			q = x;
		}
	}
	assert(mx != perm.size());
	if (q[3] >= 0){
		int tmp = getNextLightest(q[0]+1, q[1]+1, q[2]+1, q[3]+1) - 1;
		for (int i = 0; i < 3; i++){
			if (tmp == q[i]) perm = ans[i];
		}
	}
	else{
		int tmp;
		switch(q[3]){
			case -1:
				tmp = getLightest(q[0]+1, q[1]+1, q[2]+1)-1;
				break;
			case -2:
				tmp = getMedian(q[0]+1, q[1]+1, q[2]+1)-1;
				break;
			case -3:
				tmp = getHeaviest(q[0]+1, q[1]+1, q[2]+1)-1;
				break;
		}
		for (int i = 0; i < 3; i++){
			if (tmp == q[i]) perm = ans[i];
		}
	}
	solve();
}

int cnt = 0;

void orderCoins() {
	cnt++;
	debug(cnt);
	vector<int> tmp = {0, 1, 2, 3, 4, 5};

	perm.clear();
	
	do{
		perm.push_back(tmp);
	} while(next_permutation(all(tmp)));

	//debug(perm.size());

	solve();
	int ans[6];
	for (int i = 0; i < 6; i++) ans[perm[0][i]] = i+1;
	answer(ans);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:29:15: warning: unused parameter 'T' [-Wunused-parameter]
   29 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void solve()':
scales.cpp:85:23: warning: conversion from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   85 |  int mx = perm.size() + 1;
      |           ~~~~~~~~~~~~^~~
scales.cpp:103:16: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
  103 |   int tmp = max({res[0].size(), res[1].size(), res[2].size()});
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from scales.cpp:2:
scales.cpp:112:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  assert(mx != perm.size());
      |         ~~~^~~~~~~~~~~~~~
scales.cpp: In function 'int get(std::vector<int>, int, int, int, int)':
scales.cpp:54:37: warning: control reaches end of non-void function [-Wreturn-type]
   54 |  vector<int> tmp = {a[x], a[y], a[z]};
      |                                     ^
scales.cpp: In function 'int getnext(std::vector<int>, int, int, int, int)':
scales.cpp:62:37: warning: control reaches end of non-void function [-Wreturn-type]
   62 |  vector<int> tmp = {a[x], a[y], a[z]};
      |                                     ^
scales.cpp: In function 'void solve()':
scales.cpp:133:4: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
  133 |    if (tmp == q[i]) perm = ans[i];
      |    ^~

• Subtask 1: 100 / 100