Submission #1056605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056605		MercubytheFirst	Prisoner Challenge (IOI22_prison)	C++17	47 / 100	9 ms	1372 KiB

prison

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


const int B = 3;
const int x = 32;
const int L = 8;

int get_ith_dig(int n, int i) {
  for(int j = 0; j < i; ++j) {
    n /= B;
  }
  return n % B;
}

// [L][B]

vector<vector<int>> devise_strategy(int N) {
  vector<vector<int> > ans(x + 1, vector<int>(N + 1));
  ans[0][0] = 0;
  for(int i = 1; i <= N; ++i) {
    int dig = get_ith_dig(i, L - 1);
    ans[0][i] = (L - 1) * B + dig + 1;
  }
  for(int saw = 1; saw <= x; ++saw) {
    if(saw <= B*L) {
      int check_dig = (saw - 1) / B, a_dig = (saw - 1) % B;
      ans[saw][0] = 1;
      for(int inbag = 1; inbag <= N; ++inbag) {
        const int d = get_ith_dig(inbag, check_dig);
        if(d < a_dig) {
          ans[saw][inbag] = -2;
        }
        else if(d > a_dig) {
          ans[saw][inbag] = -1;
        }
        else {
          ans[saw][inbag] = B * L + check_dig;
        }
      }
    }
    else {
      int to_check = saw - B * L;
      ans[saw][0] = 0;
      for(int inbag = 1; inbag <= N; ++inbag) {
        ans[saw][inbag] = (to_check - 1) * B + get_ith_dig(inbag, to_check - 1) + 1;
      }
    }
  }
  // for(int i = 0; i <= x; ++i) {
  //   cout << i << " : ";
  //   for(int j = 0; j <= N; ++j) {
  //     cout << ans[i][j] << ' ';
  //   }cout << endl;
  // }
  return ans;
}

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