Submission #1179735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179735		catch_me_if_you_can	Prisoner Challenge (IOI22_prison)	C++20	80 / 100	6 ms	1096 KiB

prison

#include<bits/stdc++.h>
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back

vector<vector<int>> devise_strategy(int N)
{
  int X = 24;
  int Xp = 22; 
  vector<int> hsh(25);//takes stuff from 0 to 24 and tells you compressed val
  vector<int> ok(23);//takes stuff from 0 to 22 and tells you uncompressed val
  hsh[0] = 0;
  hsh[1] = -1;
  hsh[2] = 1;
  hsh[3] = -1;
  ok[0] = 0;
  ok[1] = 2;
  for(int i = 4; i <= 24; i++){
    hsh[i] = i-2;
    ok[i-2] = i;
  }
  vector<vector<int>> s(Xp+1);
  vector<int> p3(9, 1);
  for(int i = 1; i <= 8; i++)
    p3[i] = 3*p3[i-1];
  //cout << "Wtf" << endl;
  //0 ? -> 0
  //1 ? -> 1
  //2 ? -> 2
  //0, 1, 2, 3, 4, 5, 6, 7
  s[0].resize(N+1);
  s[0][0] = 0;//Check A.
  for(int i = 1; i <= N; i++)
    s[0][i] = hsh[22 + ((i/p3[7])%3)];
  //cout << "Wtf" << endl; 
  for(int i = 0; i < Xp; i++)
  {
    //cout << "Wtf = " << (i+1) << endl;
    //Stuff in here goes into s[i+1]
    s[i+1].resize(N+1);
    int ip = ok[i+1]-1;
    int b = (ip/3);
    int v = ip%3;
    s[i+1][0] = b%2;
    //         A B
    //b odd -> v ?
    //b even-> ? v
    for(int j = 1; j <= N; j++)
    {
      int vp = (j/p3[b])%3;
      if(vp > v)
        s[i+1][j] = -2 + (b%2);
      else if(vp < v)
        s[i+1][j] = -1 - (b%2);
      else if(b == 0)
        s[i+1][j] = 0;//this should never happen in real life play-through
      else
      {
        int D = 3*(b-1) + ((j/p3[b-1])%3) + 1;
        if(hsh[D] != -1)
          s[i+1][j] = hsh[D];
        else
        {
          if(D == 1)
            s[i+1][j] = -2;
          else
            s[i+1][j] = -1;
        }
      }
    }
  }
  return s;
}

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