Submission #784884

#TimeUsernameProblemLanguageResultExecution timeMemory
784884aZvezdaScales (IOI15_scales)C++14
0 / 100
1 ms212 KiB
#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<ll> all; ll dp[1 << MAX_N]; pair<ll, pair<pair<ll, ll>, pair<ll, ll> > > hist[1 << MAX_N]; bool valid(ll curr, ll a, ll b) { while(curr % 7 != b) { if(curr % 7 == a) { return false; } curr /= 7; } return true; } 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; } 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(all[i], a, b)) { ret += (1 << i); } } return ret; } ll encode(const vector<ll> &arr) { ll ret = 0; for(ll i = 0; i < arr.size(); i ++) { ret = ret * 7 + arr[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(new_mask, a, b); new_mask = eliminate_mask(new_mask, a, c); mx = max(mx, dp[new_mask]); } { new_mask = mask; new_mask = eliminate_mask(new_mask, b, a); new_mask = eliminate_mask(new_mask, b, c); mx = max(mx, dp[new_mask]); } { new_mask = mask; new_mask = eliminate_mask(new_mask, c, a); new_mask = eliminate_mask(new_mask, c, 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(new_mask, b, a); new_mask = eliminate_mask(new_mask, c, a); mx = max(mx, dp[new_mask]); } { new_mask = mask; new_mask = eliminate_mask(new_mask, a, b); new_mask = eliminate_mask(new_mask, c, b); mx = max(mx, dp[new_mask]); } { new_mask = mask; new_mask = eliminate_mask(new_mask, a, c); new_mask = eliminate_mask(new_mask, b, c); 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(encode(perm)); } while(next_permutation(perm.begin(), perm.end())); all = eliminate(all, 1, 2); all = eliminate(all, 2, 3); all = eliminate(all, 4, 5); all = eliminate(all, 5, 6); return; ll total = (1ll << all.size()); for(ll i = 0; i < total; i ++) { dp[i] = 1e9; if((i & (i - 1)) == 0) { dp[i] = 0; continue; } while(dp[i] > 100) { const auto rnd = []() { return rand() % 6 + 1; }; ll a = rnd(); ll b = rnd(); ll c = rnd(); while(a == b || a == c) { a = rnd(); b = rnd(); c = rnd(); } calc_lightest(i, a, b, c); } dp[i] ++; } } int W[10], trans[10], old[10]; void orderCoins() { return; { 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 small = 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[small] ); now_active = eliminate_mask( now_active, curr.second.first.second, trans[small] ); now_active = eliminate_mask( now_active, curr.second.second.first, trans[small] ); } } for(ll i = 0; i < MAX_N; i ++) { if(now_active & (1 << i)) { ll cpy = all[i]; for(ll j = 5; j >= 0; j --) { old[j] = W[cpy % 7]; cpy /= 7; } break; } } answer(old); }

Compilation message (stderr)

scales.cpp: In function 'll encode(const std::vector<long long int>&)':
scales.cpp:46: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]
   46 |  for(ll i = 0; i < arr.size(); i ++) {
      |                ~~^~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:154:15: warning: unused parameter 'T' [-Wunused-parameter]
  154 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:195:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  195 |   W[1] = small;
      |          ^~~~~
scales.cpp:196:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  196 |   W[2] = median;
      |          ^~~~~~
scales.cpp:197:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  197 |   W[3] = big;
      |          ^~~
scales.cpp:203:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  203 |   W[4] = small;
      |          ^~~~~
scales.cpp:204:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  204 |   W[5] = median;
      |          ^~~~~~
scales.cpp:205:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  205 |   W[6] = big;
      |          ^~~
scales.cpp:208:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  208 |   trans[W[i]] = i;
      |                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...