Submission #1009706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009706		oyber	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	10 ms	1116 KiB

prison

#include "prison.h"
  
#include <bits/stdc++.h>
using namespace std;

int get_index(int counter, int digit) {
  return counter*3 + digit - 1;
}

int get_counter(int index) {
  return (index+1)/3;
}

int get_digit(int index) {
  return (index+1)%3;
}

int get_num_digit(int num, int counter) {
  for (int i = 0; i < counter; i++) {
    num /= 3;
  }
  return num%3;
}

int final_bag(int bag) {
  return -(bag+1);
}

vector<vector<int>> devise_strategy(int N) {
  int n = 8*3+1-2;
  vector<vector<int>> s(n);

  for (int i = 2; i < n; i++) {
    s[i].resize(N+1);
    int counter = get_counter(i);
    int last_digit = get_digit(i);
    int bag = counter%2;
    //printf("i: %d, counter: %d, last_digit: %d, bag: %d\n", i, counter, last_digit, bag);
    s[i][0] = bag;

    for (int j = 1; j <= N; j++) {
      int digit = get_num_digit(j, counter);
      if (digit < last_digit) {
        s[i][j] = final_bag(bag);
      } else if (last_digit < digit) {
        s[i][j] = final_bag(!bag);
      } else {
        if (counter != 0) {
          int new_counter = counter-1;
          int new_digit = get_num_digit(j, new_counter);
          if (counter == 1) {
            if (new_digit == 0) {
              s[i][j] = final_bag(bag);
            } else if (new_digit == 2) {
              s[i][j] = final_bag(!bag);
            } else {
              s[i][j] = 1;
            }
            continue;
          }

          s[i][j] = get_index(new_counter, new_digit);
          //printf("index: %d, new_counter: %d, new_digit: %d\n", s[i][j], new_counter, new_digit);
          //printf("%d %d %d\n", s[i][j], new_counter, new_digit);
        }
      }
    }
  }

  s[0].resize(N+1);
  int counter = 7;
  int bag = !(counter%2);
  s[0][0] = bag;
  for (int j = 1; j <= N; j++) {
      int digit = get_num_digit(j, counter);
      s[0][j] = get_index(counter, digit);
      //printf("%d\n", s[0][j]);
  }

  s[1].resize(N+1);
  counter = 0;
  bag = counter%2;
  s[1][0] = bag;
  for (int j = 1; j <= N; j++) {
    int digit = get_num_digit(j, counter);
    //printf("%d\n", s[0][j]);
    if (digit == 0) {
      s[1][j] = final_bag(bag);
    } else {
      s[1][j] = final_bag(!bag);
    }
  }
  
  return s;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 70 / 90