제출 #784901

#제출 시각아이디문제언어결과실행 시간메모리
784901aZvezda저울 (IOI15_scales)C++17
0 / 100
1004 ms49760 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<vector<ll> > all; ll dp[1 << MAX_N]; pair<ll, pair<pair<ll, ll>, pair<ll, ll> > > hist[1 << MAX_N]; bool start_print = false; bool valid(const vector<ll> &curr, ll a, ll b) { for(int i = 0; i < curr.size(); i ++) { if(curr[i] == a) { return true; } else if(curr[i] == b) { return false; } } return true; } bool valid2_small(const vector<ll> &curr, ll a, ll b, ll c) { for(int i = 0; i < curr.size(); i ++) { if(curr[i] == a) { return true; } else if(curr[i] == b || curr[i] == c) { return false; } } return true; } bool valid2_big(const vector<ll> &curr, ll a, ll b, ll c) { for(int i = curr.size() - 1; i >= 0; i --) { if(curr[i] == a) { return true; } else if(curr[i] == b || curr[i] == c) { return false; } } return true; } vector<vector<ll> > eliminate(const vector<vector<ll> > &curr, ll a, ll b) { vector<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 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(all[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(all[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())); all = eliminate(all, 1, 2); all = eliminate(all, 2, 3); all = eliminate(all, 4, 5); all = eliminate(all, 5, 6); 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_print = 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); }

컴파일 시 표준 에러 (stderr) 메시지

scales.cpp: In function 'bool valid(const std::vector<long long int>&, ll, ll)':
scales.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i = 0; i < curr.size(); i ++) {
      |                 ~~^~~~~~~~~~~~~
scales.cpp: In function 'bool valid2_small(const std::vector<long long int>&, ll, ll, ll)':
scales.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i = 0; i < curr.size(); i ++) {
      |                 ~~^~~~~~~~~~~~~
scales.cpp: In function 'bool valid2_big(const std::vector<long long int>&, ll, ll, ll)':
scales.cpp:38:26: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   38 |  for(int i = curr.size() - 1; i >= 0; i --) {
      |              ~~~~~~~~~~~~^~~
scales.cpp: In function 'void init(int)':
scales.cpp:184:15: warning: unused parameter 'T' [-Wunused-parameter]
  184 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:221:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  221 |   W[1] = small;
      |          ^~~~~
scales.cpp:222:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  222 |   W[2] = median;
      |          ^~~~~~
scales.cpp:223:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  223 |   W[3] = big;
      |          ^~~
scales.cpp:229:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  229 |   W[4] = small;
      |          ^~~~~
scales.cpp:230:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  230 |   W[5] = median;
      |          ^~~~~~
scales.cpp:231:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  231 |   W[6] = big;
      |          ^~~
scales.cpp:234:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  234 |   trans[W[i]] = i;
      |                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...