Submission #787066

#	Time	Username	Problem	Language	Result	Execution time	Memory
787066		GusterGoose27	Scales (IOI15_scales)	C++17	100 / 100	43 ms	744 KiB

scales

#include "scales.h"

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> all_strats;
typedef pair<int, int> pii;
bool vis[6];
int pow3[10];

void make_strats(vector<int> &v) {
	if (v.size() == 6) {
		all_strats.push_back(v);
		return;
	}
	for (int i = 0; i < 6; i++) {
		if (vis[i]) continue;
		vis[i] = 1;
		v.push_back(i);
		make_strats(v);
		v.pop_back();
		vis[i] = 0;
	}
}

int light(int a, int b, int c, vector<int> &v) {
	int s = a;
	if (v[b] < v[s]) s = b;
	if (v[c] < v[s]) s = c;
	return s;
}

int heavy(int a, int b, int c, vector<int> &v) {
	int s = a;
	if (v[b] > v[s]) s = b;
	if (v[c] > v[s]) s = c;
	return s;
}

int med(int a, int b, int c, vector<int> &v) {
	int l = light(a, b, c, v);
	int h = heavy(a, b, c, v);
	return a^b^c^l^h;
	// if (l == b) {
	// 	swap(a, b);
	// }
	// if (l == c) swap(a, c);
	// if (v[b] < v[c]) return b;
	// return c;
}

int next_light(int a, int b, int c, int d, vector<int> &v) {
	vector<pii> elems;
	elems.push_back(pii(v[a], a));
	elems.push_back(pii(v[b], b));
	elems.push_back(pii(v[c], c));
	elems.push_back(pii(v[d], d));
	sort(elems.begin(), elems.end());
	int p;
	for (int i = 0; i < 4; i++) {
		if (elems[i].second == d) {
			p = i;
			break;
		}
	}
	if (p == 3) return elems[0].second;
	return elems[p+1].second;
}

class query {
public:
	vector<int> nxt_states;
	int tp;
	vector<int> queried;
	vector<int> perm;
	query(vector<int> &nxt, int t = -1, int a = -1, int b = -1, int c = -1, int d = -1) {
		if (c == -1) {
			tp = -1;
			perm = nxt;
			return;
		}
		nxt_states = nxt;
		tp = t;
		queried.push_back(a+1);
		queried.push_back(b+1);
		queried.push_back(c+1);
		if (t == 3) queried.push_back(d+1);
	}
};

vector<query> query_res;

bool find_split(vector<int> &strats, int depth = 6) {
	if (depth == 0) {
		assert(strats.size() <= 1);
		if (strats.size() == 1) query_res.push_back(all_strats[strats[0]]);
		return 1;
	}
	for (int a = 0; a < 4; a++) {
		for (int b = a+1; b < 5; b++) {
			for (int c = b+1; c < 6; c++) {
				for (int tp = 0; tp <= 3; tp++) {
					for (int d = 0; d < ((tp < 3) ? 1 : 6); d++) {
						if (tp == 3 && (d == a || d == b || d == c)) continue;
						vector<int> g1;
						vector<int> g2;
						vector<int> g3;
						for (int cur: strats) {
							int res;
							if (tp == 0) res = light(a, b, c, all_strats[cur]);
							if (tp == 1) res = heavy(a, b, c, all_strats[cur]);
							if (tp == 2) res = med(a, b, c, all_strats[cur]);
							if (tp == 3) res = next_light(a, b, c, d, all_strats[cur]);
							if (res == a) g1.push_back(cur);
							if (res == b) g2.push_back(cur);
							if (res == c) g3.push_back(cur);
						}
						if (g1.size() > pow3[depth-1] || g2.size() > pow3[depth-1] || g3.size() > pow3[depth-1]) continue;
						bool g = 1;
						vector<int> ids;
						if (!g) continue;
						else {
							g = find_split(g1, depth-1);
							ids.push_back(query_res.size()-1);
						}
						if (!g) continue;
						else {
							g = find_split(g2, depth-1);
							ids.push_back(query_res.size()-1);
						}
						if (!g) continue;
						else {
							g = find_split(g3, depth-1);
							ids.push_back(query_res.size()-1);
						}
						if (g) {
							query_res.push_back(query(ids, tp, a, b, c, d));
							return 1;
						}
					}
				}
			}
		}
	}
	return 0;
}

void init(int t) {
	pow3[0] = 1;
	for (int i = 1; i < 10; i++) pow3[i] = 3*pow3[i-1];
	vector<int> v;
	make_strats(v);
	vector<int> strats(all_strats.size());
	iota(strats.begin(), strats.end(), 0);
	find_split(strats);
}

void orderCoins() {
	int cur = query_res.size()-1;
	for (int i = 0; i < 6; i++) {
		int res;
		int a = query_res[cur].queried[0], 
			b = query_res[cur].queried[1], 
			c = query_res[cur].queried[2], 
			d = (query_res[cur].tp == 3 ? query_res[cur].queried[3] : 0);
		if (query_res[cur].tp == 0) res = getLightest(a, b, c);
		if (query_res[cur].tp == 1) res = getHeaviest(a, b, c);
		if (query_res[cur].tp == 2) res = getMedian(a, b, c);
		if (query_res[cur].tp == 3) res = getNextLightest(a, b, c, d);
		if (res == a) cur = query_res[cur].nxt_states[0];
		if (res == b) cur = query_res[cur].nxt_states[1];
		if (res == c) cur = query_res[cur].nxt_states[2];
	}
	int ans[6];
	for (int i = 0; i < 6; i++) ans[query_res[cur].perm[i]] = i+1;
	answer(ans);
}

Compilation message (stderr)

scales.cpp: In function 'bool find_split(std::vector<int>&, int)':
scales.cpp:119:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |       if (g1.size() > pow3[depth-1] || g2.size() > pow3[depth-1] || g3.size() > pow3[depth-1]) continue;
      |           ~~~~~~~~~~^~~~~~~~~~~~~~~
scales.cpp:119:50: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |       if (g1.size() > pow3[depth-1] || g2.size() > pow3[depth-1] || g3.size() > pow3[depth-1]) continue;
      |                                        ~~~~~~~~~~^~~~~~~~~~~~~~~
scales.cpp:119:79: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |       if (g1.size() > pow3[depth-1] || g2.size() > pow3[depth-1] || g3.size() > pow3[depth-1]) continue;
      |                                                                     ~~~~~~~~~~^~~~~~~~~~~~~~~
scales.cpp:125:38: warning: conversion from 'std::vector<query>::size_type' {aka 'long unsigned int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
  125 |        ids.push_back(query_res.size()-1);
      |                      ~~~~~~~~~~~~~~~~^~
scales.cpp:130:38: warning: conversion from 'std::vector<query>::size_type' {aka 'long unsigned int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
  130 |        ids.push_back(query_res.size()-1);
      |                      ~~~~~~~~~~~~~~~~^~
scales.cpp:135:38: warning: conversion from 'std::vector<query>::size_type' {aka 'long unsigned int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
  135 |        ids.push_back(query_res.size()-1);
      |                      ~~~~~~~~~~~~~~~~^~
scales.cpp: In function 'void init(int)':
scales.cpp:149:15: warning: unused parameter 't' [-Wunused-parameter]
  149 | void init(int t) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:160:28: warning: conversion from 'std::vector<query>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  160 |  int cur = query_res.size()-1;
      |            ~~~~~~~~~~~~~~~~^~
scales.cpp:173:3: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  173 |   if (res == c) cur = query_res[cur].nxt_states[2];
      |   ^~
scales.cpp: In function 'int next_light(int, int, int, int, std::vector<int>&)':
scales.cpp:68:16: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |  return elems[p+1].second;
      |               ~^~
scales.cpp: In function 'bool find_split(std::vector<int>&, int)':
scales.cpp:116:8: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  116 |        if (res == b) g2.push_back(cur);
      |        ^~

• Subtask 1: 100 / 100