| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 784880 | aZvezda | 저울 (IOI15_scales) | C++14 | 1093 ms | 32656 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef LOCAL
#define cerr if(false)cerr
#endif
const int 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, int a, int b) {
while(curr % 7 != b) {
if(curr % 7 == a) {
return false;
}
curr /= 7;
}
return true;
}
vector<ll> eliminate(const vector<ll> &curr, int a, int b) {
assert(a != 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, int a, int b) {
ll ret = 0;
for(int 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(int i = 0; i < arr.size(); i ++) {
ret = ret * 7 + arr[i];
}
return ret;
}
ll calc_lightest(int mask, int a, int b, int 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(int mask, int a, int b, int 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(int mask, int a, int b, int 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);
for(int i = 0; i < all.size(); i ++) {
ll curr = all[i];
vector<int> ret = {};
while(curr) {
ret.push_back(curr % 7);
curr /= 7;
}
reverse(ret.begin(), ret.end());
}
ll total = (1ll << all.size());
for(int 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; };
int a = rnd();
int b = rnd();
int c = rnd();
while(a == b || a == c) {
a = rnd(); b = rnd(); c = rnd();
}
calc_lightest(i, a, b, c);
calc_heaviest(i, a, b, c);
}
dp[i] ++;
}
}
int W[10], trans[10], old[10];
void orderCoins() {
{
int small = getLightest(1, 2, 3);
int median = getMedian(1, 2, 3);
int big = (1 + 2 + 3) - (small + median);
W[1] = small;
W[2] = median;
W[3] = big;
}
{
int small = getLightest(4, 5, 6);
int median = getMedian(4, 5, 6);
int big = (4 + 5 + 6) - (small + median);
W[4] = small;
W[5] = median;
W[6] = big;
}
for(int 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) {
int 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) {
int 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(int i = 0; i < MAX_N; i ++) {
if(now_active & (1 << i)) {
ll cpy = all[i];
for(int j = 5; j >= 0; j --) {
old[j] = W[cpy % 7];
cpy /= 7;
}
break;
}
}
answer(old);
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||