제출 #1180034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180034		Kanon	버섯 세기 (IOI20_mushrooms)	C++20	컴파일 에러	0 ms	0 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);

const int N = 150;
vector<vector<int>> explore_cost_of_tokens_with_A_sum(N + 1, vector<int>(N + 1, INT_MAX));
vector<vector<int>> Try_to_explore_tokens(N + 1, vector<int>(N + 1, -1));

void prepare_explore() {
  explore_cost_of_tokens_with_A_sum[0][0] = 0;
  for (int tokens = 1; tokens <= N; tokens++) {
    for (int A_sum = 0; A_sum <= tokens; A_sum++) {
      if (A_sum == 0 || A_sum == tokens) explore_cost_of_tokens_with_A_sum[tokens][A_sum] = 0;
      else {
        for (int try_tokens = 1; try_tokens < tokens; try_tokens++) {
          int worst_cost = 0;
          for (int what_A = 0; what_A <= min(A_sum, try_tokens); what_A++) {
            if (what_A > 0) {
              worst_cost = max(worst_cost, explore_cost_of_tokens_with_A_sum[try_tokens - 1][what_A - 1] + 1 + explore_cost_of_tokens_with_A_sum[tokens - try_tokens][A_sum - what_A]);
            }
            if (what_A < try_tokens) {
              worst_cost = max(worst_cost, explore_cost_of_tokens_with_A_sum[try_tokens - 1][what_A] + 1 + explore_cost_of_tokens_with_A_sum[tokens - try_tokens][A_sum - what_A]);
            }
          }
          if (explore_cost_of_tokens_with_A_sum[tokens][A_sum] > worst_cost) {
            Try_to_explore_tokens[tokens][A_sum] = try_tokens;
            explore_cost_of_tokens_with_A_sum[tokens][A_sum] = worst_cost;
          }
        }
      }
    }
  }
}

vector<int> mushrooms;
int used = 0;
int pre = 0;

int use_machine(vector<int> x) {
  used++;
  int ret = 0;
  for (int i : x) if (mushrooms[i] == -1) {
    mushrooms[i] = pre ^ 1;
    pre ^= 1;
  }
  for (int i = 0; i < int(x.size()) - 1; i++) {
    ret += (mushrooms[x[i]] != mushrooms[x[i + 1]]);
  }
  return ret;
}

vector<int> Merge(vector<int> base, vector<int> Eval) {
  assert(Eval.size() <= base.size());
  vector<int> ret(Eval.size() + base.size());
  int id = ret.size() - 1;
  while (id >= 0) {
    if (Eval.size()) {
      ret[id--] = Eval.back();
      Eval.pop_back();
    }
    ret[id--] = base.back();
    base.pop_back();
  }
  return ret;
};

tuple<int, int, int, int> calc(vector<int> A_know, vector<int> B_know, vector<int> evaluating_tokens) {
  assert(evaluating_tokens.size());
  assert(evaluating_tokens.size() <= max(A_know.size(), B_know.size()));

  int last_token = evaluating_tokens.back();
  int last_token_value = -1;
  int total_A_zero = 0;
  int total_B_one = 0;

  if (A_know.size() >= B_know.size()) {
    int val = use_machine(Merge(A_know, evaluating_tokens));
    last_token_value = val & 1;
    total_B_one = val - (val & 1) >> 1;
    total_A_zero = evaluating_tokens.size() - 1 - total_B_one;
  } else {
    int val = use_machine(Merge(B_know, evaluating_tokens));
    last_token_value = val & 1 ^ 1;
    total_A_zero = val - (val & 1) >> 1;
    total_B_one = evaluating_tokens.size() - 1 - total_A_zero;
  }
  return make_tuple(total_A_zero, total_B_one, last_token, last_token_value);
}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// generate random number between l, r : uniform_int_distribution<long long>(l, r)(rng)
// random shuffle : shuffle(.begin(), .end(), rng)

pair<vector<int>, vector<int>> Exploring(vector<int> A_know, vector<int> B_know, vector<int> evaluating_tokens, int total_A_zero) {
  vector<int> A_ret;
  vector<int> B_ret;
  shuffle(evaluating_tokens.begin(), evaluating_tokens.end(), rng);
  if (total_A_zero == int(evaluating_tokens.size())) {
    A_ret = evaluating_tokens;
    return make_pair(A_ret, B_ret);
  } else if (total_A_zero == 0) {
    B_ret = evaluating_tokens;
    return make_pair(A_ret, B_ret);
  }
  int tokens = evaluating_tokens.size();
  int A_sum = total_A_zero;
  assert(tokens <= N);
  int try_tokens = tokens / 2;
  if (try_tokens & 1 && tokens & 1) try_tokens++;
  assert(try_tokens > 0 && try_tokens < tokens);
  vector<int> Trying_tokens = vector<int>(evaluating_tokens.begin(), evaluating_tokens.begin() + try_tokens);
  vector<int> Left_tokens = vector<int>(evaluating_tokens.begin() + try_tokens, evaluating_tokens.end());
  auto [Trying_A_zeros, Trying_B_ones, last_token, last_token_value] = calc(A_know, B_know, Trying_tokens);
  if (last_token_value == 0) A_ret.push_back(last_token);
  else B_ret.push_back(last_token);
  Trying_tokens.pop_back();
  auto [AA, BB] = Exploring(A_know, B_know, Trying_tokens, Trying_A_zeros);
  auto [AAA, BBB] = Exploring(A_know, B_know, Left_tokens, total_A_zero - (last_token_value == 0) - Trying_A_zeros);
  for (int i : AA) A_ret.push_back(i);
  for (int i : AAA) A_ret.push_back(i);
  for (int i : BB) B_ret.push_back(i);
  for (int i : BBB) B_ret.push_back(i);
  return make_pair(A_ret, B_ret);
}

int total_A = 1;

void Absorb(vector<int> &A_know, vector<int> &B_know, vector<int> evaluating_tokens) {
  assert(evaluating_tokens.size());
  auto [total_A_zero, total_B_one, last_token, last_token_value] = calc(A_know, B_know, evaluating_tokens);
  evaluating_tokens.pop_back();
  if (last_token_value == 0) A_know.push_back(last_token);
  else B_know.push_back(last_token);
  auto [A, B] = Exploring(A_know, B_know, evaluating_tokens, total_A_zero);
  for (int i : A) A_know.push_back(i);
  for (int i : B) B_know.push_back(i);
  total_A += A.size() + (last_token_value == 0);
}

int skip_to_max = 60;

int count_mushrooms(int n) {
  prepare_explore();

  vector<int> A_know = {0};
  vector<int> B_know;
  vector<int> untouched(n - 1);
  iota(untouched.begin(), untouched.end(), 1);
  shuffle(untouched.begin(), untouched.end(), rng);
  int ptr = 0;

  if (n <= 220) {
    while (ptr < n - 1) {
      vector<int> foo = {untouched[ptr]};
      Absorb(A_know, B_know, foo);
      ptr++;
    }
    return total_A;
  }

  while (max(A_know.size(), B_know.size()) < skip_to_max) {
    int try_tokens = max(A_know.size(), B_know.size());
    try_tokens = min(try_tokens, 2 * skip_to_max - int(A_know.size() + B_know.size()));
    if (try_tokens & 1 && try_tokens > 1) try_tokens--;
    vector<int> foo = vector<int>(untouched.begin() + ptr, untouched.begin() + ptr + try_tokens);
    int pre_used = used;
    ptr += try_tokens;
    Absorb(A_know, B_know, foo);
  }

  while (ptr < n - 1) {
    int try_tokens = max(A_know.size(), B_know.size());
    try_tokens = min(try_tokens, n - 1 - ptr);
    vector<int> foo = vector<int>(untouched.begin() + ptr, untouched.begin() + ptr + try_tokens);
    ptr += try_tokens;
    auto [total_A_zero, total_B_one, last_token, last_token_value] = calc(A_know, B_know, foo);
    total_A += total_A_zero + (last_token_value == 0);
    if (last_token_value == 0) A_know.push_back(last_token);
    else B_know.push_back(last_token);
  }
  return total_A;
}

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

/usr/bin/ld: /tmp/cc855Hcn.o: in function `use_machine(std::vector<int, std::allocator<int> >)':
stub.cpp:(.text+0x150): multiple definition of `use_machine(std::vector<int, std::allocator<int> >)'; /tmp/ccL0CVUo.o:mushrooms.cpp:(.text+0x4c0): first defined here
collect2: error: ld returned 1 exit status