Submission #1279717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279717		sheercold	Koala Game (APIO17_koala)	C++20	47 / 100	59 ms	456 KiB

koala

#include "koala.h"

#include <bits/stdc++.h>

using namespace std;

int minValue(int N, int W) {
  assert(N == W);
  int input[100];
  int output[100];
  fill(input, input + 100, 0);
  input[0] = 1;
  playRound(input, output);
  for (int i = 0; i < N; i++) {
    if (output[i] == 0) {
      return i;
    }
  }
  return 0;
}

int maxValue(int N, int W) {
  assert(N == W);
  int input[100];
  int output[100];
  vector<int> big(N);
  iota(big.begin(), big.end(), 0);
  while (big.size() > 1) {
    fill(input, input + 100, 0);
    int can_add = W / big.size();
    can_add = min(can_add, 13);
    for (int ind : big) {
      input[ind] = can_add;
    }
    playRound(input, output);
    vector<int> nbig;
    for (int ind : big) {
      if (output[ind] > input[ind]) {
        nbig.push_back(ind);
      }
    }
    swap(big, nbig);
  }
  assert(big.size() == 1);
  return big[0];
}

int greaterValue(int N, int W) {
  assert(N == W);
  assert(W >= 3);
  int input[100];
  int output[100];
  fill(input, input + 100, 0);
  auto check_result = [&]() -> int {
    array<int, 2> big;
    big[0] = input[0] < output[0];
    big[1] = input[1] < output[1];
    if (big[0] ^ big[1]) {
      return big[0] == 0;
    } else {
      return big[0] + 2;
    }
  };
  input[0] = input[1] = 3;
  playRound(input, output);
  int res = check_result();
  if (res < 2) {
    return res;
  }
  res -= 2;
  if (res == 0) {
    input[0] = input[1] = 2;
    playRound(input, output);
    res = check_result();
    if (res < 2) {
      return res;
    }
    res -= 2;
    assert(res == 0);
    input[0] = input[1] = 1;
    playRound(input, output);
    res = check_result();
    assert(res < 2);
    return res;
  } else {
    input[0] = input[1] = 5;
    playRound(input, output);
    res = check_result();
    if (res < 2) {
      return res;
    }
    res -= 2;
    assert(res == 1);
    input[0] = input[1] = 8;
    playRound(input, output);
    res = check_result();
    assert(res < 2);
    return res;
  }
  return 0;
}

void allValues(int N, int W, int *P) {
  int input[100];
  int output[100];
  if (W == 2*N) {
    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    stable_sort(order.begin(), order.end(), [&](int lhs, int rhs) -> bool {
      fill(input, input + 100, 0);
      input[lhs] = input[rhs] = N;
      playRound(input, output);
      return input[rhs] < output[rhs];
    });
    for (int i = 0; i < N; i++) {
      P[order[i]] = i + 1;
    }
  } else {
    // TODO: Implement Subtask 5 solution here.
    // You may leave this block unmodified if you are not attempting this
    // subtask.
  }
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 0 / 53