Submission #719205

#	Time	Username	Problem	Language	Result	Execution time	Memory
719205		veehz	Prisoner Challenge (IOI22_prison)	C++17	56 / 100	15 ms	1204 KiB

prison

#include "prison.h"

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

int get_num(int digit, int pos) { return 3 * pos + digit + 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(27, 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);
        }
      }
    }
  }

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

  return strategy;
}

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