| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 784908 |
2023-07-16T18:07:56 Z |
aZvezda |
Scales (IOI15_scales) |
C++17 |
|
710 ms |
49828 KB |
#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
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;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
683 ms |
49628 KB |
Output is partially correct |
| 2 |
Partially correct |
681 ms |
49564 KB |
Output is partially correct |
| 3 |
Partially correct |
668 ms |
49588 KB |
Output is partially correct |
| 4 |
Partially correct |
666 ms |
49828 KB |
Output is partially correct |
| 5 |
Partially correct |
686 ms |
49600 KB |
Output is partially correct |
| 6 |
Partially correct |
687 ms |
49672 KB |
Output is partially correct |
| 7 |
Partially correct |
670 ms |
49652 KB |
Output is partially correct |
| 8 |
Partially correct |
699 ms |
49612 KB |
Output is partially correct |
| 9 |
Partially correct |
697 ms |
49788 KB |
Output is partially correct |
| 10 |
Partially correct |
671 ms |
49656 KB |
Output is partially correct |
| 11 |
Partially correct |
661 ms |
49664 KB |
Output is partially correct |
| 12 |
Partially correct |
669 ms |
49648 KB |
Output is partially correct |
| 13 |
Partially correct |
702 ms |
49624 KB |
Output is partially correct |
| 14 |
Partially correct |
686 ms |
49544 KB |
Output is partially correct |
| 15 |
Partially correct |
665 ms |
49756 KB |
Output is partially correct |
| 16 |
Partially correct |
672 ms |
49648 KB |
Output is partially correct |
| 17 |
Partially correct |
663 ms |
49616 KB |
Output is partially correct |
| 18 |
Partially correct |
710 ms |
49612 KB |
Output is partially correct |
| 19 |
Partially correct |
689 ms |
49656 KB |
Output is partially correct |
| 20 |
Partially correct |
702 ms |
49632 KB |
Output is partially correct |
| 21 |
Partially correct |
664 ms |
49572 KB |
Output is partially correct |
| 22 |
Partially correct |
664 ms |
49596 KB |
Output is partially correct |
| 23 |
Partially correct |
681 ms |
49660 KB |
Output is partially correct |
| 24 |
Partially correct |
669 ms |
49608 KB |
Output is partially correct |
| 25 |
Partially correct |
680 ms |
49716 KB |
Output is partially correct |
| 26 |
Partially correct |
682 ms |
49612 KB |
Output is partially correct |
| 27 |
Partially correct |
666 ms |
49568 KB |
Output is partially correct |
| 28 |
Partially correct |
668 ms |
49740 KB |
Output is partially correct |
| 29 |
Partially correct |
672 ms |
49672 KB |
Output is partially correct |
| 30 |
Partially correct |
675 ms |
49640 KB |
Output is partially correct |
| 31 |
Partially correct |
665 ms |
49636 KB |
Output is partially correct |
| 32 |
Partially correct |
668 ms |
49612 KB |
Output is partially correct |
| 33 |
Partially correct |
668 ms |
49628 KB |
Output is partially correct |
| 34 |
Partially correct |
670 ms |
49620 KB |
Output is partially correct |
| 35 |
Partially correct |
670 ms |
49668 KB |
Output is partially correct |
| 36 |
Partially correct |
675 ms |
49660 KB |
Output is partially correct |
| 37 |
Partially correct |
676 ms |
49616 KB |
Output is partially correct |
| 38 |
Partially correct |
665 ms |
49636 KB |
Output is partially correct |
| 39 |
Partially correct |
667 ms |
49596 KB |
Output is partially correct |
| 40 |
Partially correct |
690 ms |
49784 KB |
Output is partially correct |
