제출 #1009703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009703		oyber	죄수들의 도전 (IOI22_prison)	C++17	65 / 100	9 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;
  vector<vector<int>> s(n);

  for (int i = 1; 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);
          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]);
  }
  
  return s;
}

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