oj.uz

답안 #237987

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
237987 2020-06-09T14:57:21 Z rama_pang 저울 (IOI15_scales) C++14
100 / 100
 727 ms 508 KB 
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 720;
using state = bitset<N>;

vector<vector<int>> combinations; // take 4 coins' ids
vector<vector<int>> permutations; // weights of each coin

function<int(int, int, int, int, int)> Lightest = [&](int P, int A, int B, int C, int D) {
  if (P == -1) {
    return getLightest(A + 1, B + 1, C + 1) - 1;
  } else {
    const vector<int> &cur = permutations[P];
    vector<array<int, 2>> weights = {{cur[A], A}, {cur[B], B}, {cur[C], C}};
    sort(begin(weights), end(weights));
    return weights[0][1];
  }
};

function<int(int, int, int, int, int)> Median = [&](int P, int A, int B, int C, int D) {
  if (P == -1) {
    return getMedian(A + 1, B + 1, C + 1) - 1;
  } else {
    const vector<int> &cur = permutations[P];
    vector<array<int, 2>> weights = {{cur[A], A}, {cur[B], B}, {cur[C], C}};
    sort(begin(weights), end(weights));
    return weights[1][1];
  }
};

function<int(int, int, int, int, int)> Heaviest = [&](int P, int A, int B, int C, int D) {
  if (P == -1) {
    return getHeaviest(A + 1, B + 1, C + 1) - 1;
  } else {
    const vector<int> &cur = permutations[P];
    vector<array<int, 2>> weights = {{cur[A], A}, {cur[B], B}, {cur[C], C}};
    sort(begin(weights), end(weights));
    return weights[2][1];
  }
};

function<int(int, int, int, int, int)> NextLightest = [&](int P, int A, int B, int C, int D) {
  if (P == -1) {
    return getNextLightest(A + 1, B + 1, C + 1, D + 1) - 1;
  } else {
    const vector<int> &cur = permutations[P];
    vector<array<int, 2>> weights = {{cur[A], A}, {cur[B], B}, {cur[C], C}};
    sort(begin(weights), end(weights));
    if (cur[D] < weights[0][0]) return weights[0][1];
    if (cur[D] < weights[1][0]) return weights[1][1];
    if (cur[D] < weights[2][0]) return weights[2][1];
    return weights[0][1];
  }
};

void init(int T) {
  for (int mask = 0; mask < (1 << 6); mask++) {
    if (__builtin_popcount(mask) == 4) {
      vector<int> active;
      for (int i = 0; i < 6; i++) {
        if (mask & (1 << i)) {
          active.emplace_back(i);
        }
      }
      do {
        combinations.emplace_back(active);
      } while (next_permutation(begin(active), end(active)));
    }
  }

  vector<int> p = {0, 1, 2, 3, 4, 5};
  do {
    permutations.emplace_back(p);
  } while (next_permutation(begin(p), end(p)));
}

bool Solve(const state &candidates, int depth);

bool Try(const state &perms, const function<int(int, int, int, int, int)> &f, int depth) {
  for (auto &comb : combinations) {
    int mx = 0;
    for (int ans = 0; ans < 4; ans++) {
      int can = 0;
      for (int p = 0; p < N; p++) if (perms[p]) {
        if (f(p, comb[0], comb[1], comb[2], comb[3]) == comb[ans]) {
          can++;
        }
      }
      mx = max(mx, can);
    }

    int cnt = perms.count();
    bool transition = false;
    if (243 < cnt && cnt <= 720) transition |= mx <= 240;
    if (81  < cnt && cnt <= 243) transition |= mx <= 81;
    if (27  < cnt && cnt <=  81) transition |= mx <= 27;
    if (9   < cnt && cnt <=  27) transition |= mx <= 9;
    if (3   < cnt && cnt <=   9) transition |= mx <= 3;
    if (0   < cnt && cnt <=   3) transition |= mx <= 1;
    if (transition) {
      int ans = f(-1, comb[0], comb[1], comb[2], comb[3]);
      state can = 0;
      for (int p = 0; p < N; p++) if (perms[p]) {
        if (f(p, comb[0], comb[1], comb[2], comb[3]) == ans) {
          can[p] = 1;
        }
      }
      return Solve(can, depth + 1);
    }
  }
  return false;
}

bool Solve(const state &candidates, int depth = 0) {
  if (candidates.count() == 1) {
    int pid = candidates._Find_first();
    vector<int> order(6);
    for (int i = 0; i < 6; i++) {
      order[permutations[pid][i]] = i + 1;
    }
    answer(order.data());
    return true;
  } else if (depth % 4 == 0) {
    return Try(candidates, Lightest, depth) || Try(candidates, Median, depth) || 
           Try(candidates, Heaviest, depth) || Try(candidates, NextLightest, depth);
  } else if (depth % 4 == 1) {
    return Try(candidates, Median, depth) || Try(candidates, Heaviest, depth) || 
           Try(candidates, NextLightest, depth) || Try(candidates, Lightest, depth);
  } else if (depth % 4 == 2) {
    return Try(candidates, Heaviest, depth) || Try(candidates, NextLightest, depth) ||
           Try(candidates, Lightest, depth) || Try(candidates, Median, depth);
  } else if (depth % 4 == 3) {
    return Try(candidates, NextLightest, depth) || Try(candidates, Lightest, depth) || 
           Try(candidates, Median, depth) || Try(candidates, Heaviest, depth);
  }
}

void orderCoins() {
  state candidates;
  for (int i = 0; i < N; i++) candidates[i] = 1;
  assert(Solve(candidates));
}

Compilation message

scales.cpp: In lambda function:
scales.cpp:11:87: warning: unused parameter 'D' [-Wunused-parameter]
 function<int(int, int, int, int, int)> Lightest = [&](int P, int A, int B, int C, int D) {
                                                                                       ^
scales.cpp: In lambda function:
scales.cpp:22:85: warning: unused parameter 'D' [-Wunused-parameter]
 function<int(int, int, int, int, int)> Median = [&](int P, int A, int B, int C, int D) {
                                                                                     ^
scales.cpp: In lambda function:
scales.cpp:33:87: warning: unused parameter 'D' [-Wunused-parameter]
 function<int(int, int, int, int, int)> Heaviest = [&](int P, int A, int B, int C, int D) {
                                                                                       ^
scales.cpp: In function 'void init(int)':
scales.cpp:58:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^
scales.cpp: In function 'bool Try(const state&, const std::function<int(int, int, int, int, int)>&, int)':
scales.cpp:94:26: warning: conversion to 'int' from 'std::size_t {aka long unsigned int}' may alter its value [-Wconversion]
     int cnt = perms.count();
               ~~~~~~~~~~~^~
scales.cpp: In function 'bool Solve(const state&, int)':
scales.cpp:118:37: warning: conversion to 'int' from 'std::size_t {aka long unsigned int}' may alter its value [-Wconversion]
     int pid = candidates._Find_first();
               ~~~~~~~~~~~~~~~~~~~~~~^~
scales.cpp:138:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 694 ms 384 KB Output is correct
2 Correct 702 ms 428 KB Output is correct
3 Correct 717 ms 504 KB Output is correct
4 Correct 706 ms 504 KB Output is correct
5 Correct 709 ms 384 KB Output is correct
6 Correct 709 ms 504 KB Output is correct
7 Correct 703 ms 432 KB Output is correct
8 Correct 718 ms 428 KB Output is correct
9 Correct 711 ms 504 KB Output is correct
10 Correct 708 ms 508 KB Output is correct
11 Correct 720 ms 428 KB Output is correct
12 Correct 679 ms 432 KB Output is correct
13 Correct 715 ms 384 KB Output is correct
14 Correct 697 ms 508 KB Output is correct
15 Correct 727 ms 428 KB Output is correct
16 Correct 690 ms 428 KB Output is correct
17 Correct 701 ms 384 KB Output is correct
18 Correct 706 ms 504 KB Output is correct
19 Correct 716 ms 428 KB Output is correct
20 Correct 707 ms 504 KB Output is correct
21 Correct 717 ms 504 KB Output is correct
22 Correct 691 ms 428 KB Output is correct
23 Correct 693 ms 384 KB Output is correct
24 Correct 708 ms 504 KB Output is correct
25 Correct 709 ms 504 KB Output is correct
26 Correct 718 ms 432 KB Output is correct
27 Correct 703 ms 504 KB Output is correct
28 Correct 698 ms 460 KB Output is correct
29 Correct 702 ms 384 KB Output is correct
30 Correct 711 ms 384 KB Output is correct
31 Correct 696 ms 504 KB Output is correct
32 Correct 699 ms 504 KB Output is correct
33 Correct 700 ms 504 KB Output is correct
34 Correct 694 ms 384 KB Output is correct
35 Correct 703 ms 384 KB Output is correct
36 Correct 701 ms 428 KB Output is correct
37 Correct 698 ms 504 KB Output is correct
38 Correct 698 ms 504 KB Output is correct
39 Correct 717 ms 384 KB Output is correct
40 Correct 720 ms 384 KB Output is correct