Submission #625565

#	Time	Username	Problem	Language	Result	Execution time	Memory
625565		Clan328	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	12 ms	1108 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define nL '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const ll MOD = 1e9 + 7;

void eval(bool condition) { cout << (condition ? "yes" : "no") << nL; }
void Eval(bool condition) { cout << (condition ? "Yes" : "No") << nL; }
// void EVAL(bool condition) { cout << (condition ? "YES" : "NO") << nL; }

int ipow(int a, int n) {
   if (n == 0) return 1;
   int x = ipow(a, n/2);
   if (n % 2 == 0) return x*x;
   return x*x*a;
}

template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& v) {
  for (auto elem : v) 
    stream << elem << " ";
  return stream;
}

template <typename T>
istream& operator>>(istream& stream, vector<T>& v){
   for(auto &elem : v)
    stream >> elem;
   return stream;
}

std::vector<std::vector<int>> devise_strategy(int N) {
  vvi s(25, vi(N+1));
  s[0][0] = 0;
  for (int i = 1; i <= N; i++) {
    s[0][i] = ((i>>12)&1)+1;
  }

  for (int i = 1; i <= 24; i++) {
    int bit = (((i+1)/2)-1);
    s[i][0] = bit % 2 == 0;
    for (int j = 1; j <= N; j++) {
      // if (bit == 12) {

      // }
      if (((j>>(12-bit))&1) ) {
        if (i % 2 == 1) s[i][j] = -(bit % 2)-1;
        else if (bit != 11)
          s[i][j] = (bit+2)*2 - 1 + ((j>>((12-bit)-1))&1);
        else {
          if (((j>>(12-bit-1))&1))
            s[i][j] = -(bit % 2)-1;
          else
            s[i][j] = -(bit % 2 == 0)-1;
        }
      } else {
        if (i % 2 == 0) s[i][j] = -(bit % 2 == 0)-1;
        else if (bit != 11)
          s[i][j] = (bit+2)*2 - 1 + ((j>>((12-bit)-1))&1);
        else {
          if (((j>>(12-bit-1))&1))
            s[i][j] = -(bit % 2)-1;
          else
            s[i][j] = -(bit % 2 == 0)-1;
        }
      }

      if (s[i][j] > 24) s[i][j] = 2;
    }
  }

  // cout << s[0][0] << nL;
  // cout << s[0][4] << nL;
  // cout << s[1][0] << nL;
  // cout << s[1][5] << nL;
  // cout << s[3][0] << nL;
  // cout << s[3][4] << nL;
  // cout << s[5][0] << nL;
  // cout << s[5][5] << nL;
  // cout << s[7][0] << nL;
  // cout << s[7][4] << nL;
  // cout << s[9][0] << nL;
  // cout << s[9][5] << nL;
  // cout << s[11][0] << nL;
  // cout << s[11][4] << nL;
  // cout << s[13][0] << nL;
  // cout << s[13][5] << nL;
  // cout << s[15][0] << nL;
  // cout << s[15][4] << nL;
  // cout << s[17][0] << nL;
  // cout << s[17][5] << nL;
  // cout << s[19][0] << nL;
  // cout << s[19][4] << nL;
  // cout << s[22][0] << nL;
  // cout << s[22][5] << nL;
  // cout << s[23][0] << nL;
  // cout << s[23][4] << nL;
  // for (int i = 0; i <= 24; i++) cout << s[i] << endl;

  return s;
}

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