Submission #784908

#	Time	Username	Problem	Language	Result	Execution time	Memory
784908		aZvezda	Scales (IOI15_scales)	C++17	38.54 / 100	710 ms	49828 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef LOCAL
#define cerr if(false)cerr
#endif
 
const ll MAX_N = 20;
vector<vector<ll> > all;
ll place[MAX_N][MAX_N];
ll dp[1 << MAX_N];
pair<ll, pair<pair<ll, ll>, pair<ll, ll> > > hist[1 << MAX_N]; 
bool start_prll = false;

bool valid_slow(const ll ind, ll a, ll b) {
	for(const auto it : all[ind]) {
		if(it == a) {
			return true;
		} else if(it == b) {
			return false;
		}
	}
	return true;
}
 
bool valid(const ll ind, ll a, ll b) {
	return place[ind][a] <= place[ind][b];
}
 
bool valid2_small(const ll ind, ll a, ll b, ll c) {
	return place[ind][a] <= place[ind][b] && place[ind][a] <= place[ind][c];
}
 
bool valid2_big(const ll ind, ll a, ll b, ll c) {
	return place[ind][a] >= place[ind][b] && place[ind][a] >= place[ind][c];
}
 
vector<ll> eliminate_slow(const vector<ll> &curr, ll a, ll b) {
	vector<ll > ret = {};
	for(const auto &it : curr) {
		if(valid_slow(it, a, b)) { 
			ret.push_back(it); 
		}
	}
	return ret;
}
 
vector<ll> eliminate(const vector<ll> &curr, ll a, ll b) {
	vector<ll > ret = {};
	for(const auto &it : curr) {
		if(valid(it, a, b)) { 
			ret.push_back(it); 
		}
	}
	return ret;
}

void eliminate_all(ll a, ll b) {
	vector<ll> valid = {};
	for(ll i = 0; i < all.size(); i ++) {
		valid.push_back(i);
	}
	valid = eliminate_slow(valid, a, b);
	const auto old_all = all;
	all = {};
	for(ll i = 0; i < valid.size(); i ++) {
		all.push_back(old_all[valid[i]]);
	}
}
 
ll eliminate_mask(ll mask, ll a, ll b) {
	ll ret = 0;
	for(ll i = 0; i < MAX_N; i ++) {
		if(((1 << i) & mask) && valid(i, a, b)) {
			ret += (1 << i);
		}
	}
	return ret;
}
 
ll eliminate_mask_small(ll mask, ll a, ll b, ll c) {
	ll ret = 0;
	for(ll i = 0; i < MAX_N; i ++) {
		if(((1 << i) & mask) && valid2_small(i, a, b, c)) {
			ret += (1 << i);
		}
	}
	return ret;
}
 
ll eliminate_mask_big(ll mask, ll a, ll b, ll c) {
	ll ret = 0;
	for(ll i = 0; i < MAX_N; i ++) {
		if(((1 << i) & mask) && valid2_big(i, a, b, c)) {
			ret += (1 << i);
		}
	}
	return ret;
}
 
ll calc_lightest(ll mask, ll a, ll b, ll c) {
	ll mx = 0;
	ll new_mask = mask;
 
	{
		new_mask = mask;
		new_mask = eliminate_mask_small(new_mask, a, b, c);
		mx = max(mx, dp[new_mask]);
	}
 
	{
		new_mask = mask;
		new_mask = eliminate_mask_small(new_mask, b, a, c);
		mx = max(mx, dp[new_mask]);
	}
 
	{
		new_mask = mask;
		new_mask = eliminate_mask_small(new_mask, c, a, b);
		mx = max(mx, dp[new_mask]);
	}
 
	if(mx < dp[mask]) {
		dp[mask] = mx;
		hist[mask] = {0, {{a, b}, {c, -1}}};
	}
 
	return mx;
}
 
ll calc_heaviest(ll mask, ll a, ll b, ll c) {
	ll mx = 0;
	ll new_mask = mask;
 
	{
		new_mask = mask;
		new_mask = eliminate_mask_big(new_mask, a, b, c);
		mx = max(mx, dp[new_mask]);
	}
 
	{
		new_mask = mask;
		new_mask = eliminate_mask_big(new_mask, b, a, c);
		mx = max(mx, dp[new_mask]);
	}
 
	{
		new_mask = mask;
		new_mask = eliminate_mask_big(new_mask, c, a, b);
		mx = max(mx, dp[new_mask]);
	}
 
	if(mx < dp[mask]) {
		dp[mask] = mx;
		hist[mask] = {1, {{a, b}, {c, -1}}};
	}
 
	return mx;
}
 
ll calc_median(ll mask, ll a, ll b, ll c) {
	ll mx = 0;
	ll new_mask1, new_mask2;
 
	{
		new_mask1 = eliminate_mask(mask, b, a);
		new_mask1 = eliminate_mask(mask, b, a);
		new_mask2 = eliminate_mask(mask, b, a);
		new_mask2 = eliminate_mask(mask, b, a);
		mx = max(mx, dp[new_mask1 | new_mask2]);
	}
 
	{
		new_mask1 = eliminate_mask(mask, a, b);
		new_mask1 = eliminate_mask(mask, b, c);
		new_mask2 = eliminate_mask(mask, c, b);
		new_mask2 = eliminate_mask(mask, b, a);
		mx = max(mx, dp[new_mask1 | new_mask2]);
	}
 
	{
		new_mask1 = eliminate_mask(mask, a, c);
		new_mask1 = eliminate_mask(mask, c, b);
		new_mask2 = eliminate_mask(mask, b, c);
		new_mask2 = eliminate_mask(mask, c, a);
		mx = max(mx, dp[new_mask1 | new_mask2]);
	}
 
	if(mx < dp[mask]) {
		dp[mask] = mx;
		hist[mask] = {2, {{a, b}, {c, -1}}};
	}
 
	return mx;
}
 
void init(int T) {
	vector<ll> perm = {1, 2, 3, 4, 5, 6};
	do {
		all.push_back(perm);
	} while(next_permutation(perm.begin(), perm.end()));
	eliminate_all(1, 2);
	eliminate_all(2, 3);
	eliminate_all(4, 5);
	eliminate_all(5, 6);
	
	for(ll i = 0; i < MAX_N; i ++) {
		for(ll j = 0; j < 6; j ++) {
			place[i][all[i][j]] = j;
		}
	}
	
	ll total = (1ll << all.size());
	for(ll i = 1; i < total; i ++) {
		dp[i] = 1e9;
		if((i & (i - 1)) == 0) {
			dp[i] = 0;
			continue;
		}
		while(dp[i] > 10000) {
			random_shuffle(perm.begin(), perm.end());
			ll a = perm[0];
			ll b = perm[1];
			ll c = perm[2];
			calc_lightest(i, a, b, c);
			calc_heaviest(i, a, b, c);
		}
		dp[i] ++;
	}
	start_prll = true;
}
 
int W[10], trans[10], old[10]; 
 
void orderCoins() {
	{
		ll small = getLightest(1, 2, 3);
		ll median = getMedian(1, 2, 3);
		ll big = (1 + 2 + 3) - (small + median);
		W[1] = small;
		W[2] = median;
		W[3] = big;
	}
	{
		ll small = getLightest(4, 5, 6);
		ll median = getMedian(4, 5, 6);
		ll big = (4 + 5 + 6) - (small + median);
		W[4] = small;
		W[5] = median;
		W[6] = big;
	}
	for(ll i = 1; i < 7; i ++) {
		trans[W[i]] = i;
	}
	ll now_active = (1ll << all.size()) - 1;
	while((now_active & (now_active - 1)) > 0) {
		auto curr = hist[now_active];
		if(curr.first == 0) {
			ll small = getLightest(
				W[curr.second.first.first],
				W[curr.second.first.second],
				W[curr.second.second.first]
			);
			now_active = eliminate_mask(
				now_active, 
				trans[small],
				curr.second.first.first
			);
			now_active = eliminate_mask(
				now_active, 
				trans[small],
				curr.second.first.second
			);
			now_active = eliminate_mask(
				now_active, 
				trans[small],
				curr.second.second.first
			);
		} else if(curr.first == 1) {
			ll big = getHeaviest(
				W[curr.second.first.first],
				W[curr.second.first.second],
				W[curr.second.second.first]
			);
			now_active = eliminate_mask(
				now_active, 
				curr.second.first.first,
				trans[big]
			);
			now_active = eliminate_mask(
				now_active, 
				curr.second.first.second,
				trans[big]
			);
			now_active = eliminate_mask(
				now_active, 
				curr.second.second.first,
				trans[big]
			);
		}	
	}
	for(ll i = 0; i < MAX_N; i ++) {
		if(now_active & (1 << i)) {
			for(ll j = 0; j < 6; j ++) {
				old[j] = W[all[i][j]];
			}
			break;
		}
	}
	answer(old);
}

Compilation message (stderr)

scales.cpp: In function 'void eliminate_all(ll, ll)':
scales.cpp:61:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(ll i = 0; i < all.size(); i ++) {
      |                ~~^~~~~~~~~~~~
scales.cpp:67:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(ll i = 0; i < valid.size(); i ++) {
      |                ~~^~~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:198:15: warning: unused parameter 'T' [-Wunused-parameter]
  198 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:241:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  241 |   W[1] = small;
      |          ^~~~~
scales.cpp:242:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  242 |   W[2] = median;
      |          ^~~~~~
scales.cpp:243:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  243 |   W[3] = big;
      |          ^~~
scales.cpp:249:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  249 |   W[4] = small;
      |          ^~~~~
scales.cpp:250:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  250 |   W[5] = median;
      |          ^~~~~~
scales.cpp:251:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  251 |   W[6] = big;
      |          ^~~
scales.cpp:254:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  254 |   trans[W[i]] = i;
      |                 ^

• Subtask 1: 38.541667 / 100