Submission #719554

#	Time	Username	Problem	Language	Result	Execution time	Memory
719554		veehz	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	14 ms	1020 KiB

prison

#include "prison.h"

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

int get_num(int digit, int pos) {
  if (pos < 7)
    return 3 * pos + digit + 1;
  else
    return get_num(2, 6) + 1;
}

string base3(int n) {
  string s;
  while (n) {
    s += (n % 3) + '0';
    n /= 3;
  }
  while (s.size() < 8) s += '0';
  reverse(s.begin(), s.end());
  return s;
}

int whichBag(int pos, int ifA, int ifB) {
  if (pos % 2) return ifA;
  return ifB;
}

vector<vector<int>> devise_strategy(int n) {
  vector<vector<int>> strategy(23, vector<int>(n + 1));
  for (int pos = 0; pos < 8; pos++) {
    for (int digit = 0; digit < 3; digit++) {
      int num = get_num(digit, pos);
      if (num >= 0) strategy[num][0] = whichBag(pos, 0, 1);
    }
  }

  for (int i = 1; i <= n; i++) {
    string cur = base3(i);
    strategy[0][i] = get_num(cur[0] - '0', 0);
    for (int pos = 0; pos < 8; pos++) {
      int thisDigit = cur[pos] - '0';
      for (int digit = 0; digit < 3; digit++) {
        int num = get_num(digit, pos);
        if (num >= 0) {
          if (thisDigit > digit)
            strategy[num][i] = whichBag(pos, -2,-1);
          else if (thisDigit < digit)
            strategy[num][i] = whichBag(pos, -1, -2);
          else if (thisDigit == digit && pos != 7) {
            strategy[num][i] = get_num(cur[pos + 1] - '0', pos + 1);
            if (pos == 6) {
              if(cur[pos + 1] - '0' == 0){ strategy[num][i] = -2; continue; }
              else if(cur[pos + 1] - '0' == 2) { strategy[num][i] = -1; continue; }
            }
          }
        }
      }
    }
  }

  // for(auto& v : strategy){
  //   for(auto& x : v) cout << x << " ";
  //   cout << endl;
  // }


  return strategy;
}

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