Submission #812653

#	Time	Username	Problem	Language	Result	Execution time	Memory
812653		kwongweng	Prisoner Challenge (IOI22_prison)	C++17	30 / 100	34 ms	1960 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second

vi po(9); //po[i]=3^i
int digit(int n, int pos){
  return (n%po[pos+1]) / po[pos];
}

vector<vi> devise_strategy(int N) {
  po[0]=1; FOR(i,1,9) po[i]=po[i-1]*3;
  vector<vi> ans;
  // i=0
  vi ans0(N+1); FOR(i,1,N+1){
    ans0[i]=1+digit(i,7);
  }
  ans.pb(ans0);
  FOR(i,1,8){
    FOR(j,0,3){
      vi a(N+1);
      a[0]=(i%2);
      FOR(k,1,N+1){
        int d = digit(k,8-i);
        if (d<j){
          // i%2 loses
          a[k] = -1 -(i%2);
        }
        if (d==j){
          int d2 = digit(k,7-i);
          if (i==7){
            if (d2==0) a[k]=-1-(i%2); //i%2 loses
            if (d2==2) a[k]=(i%2)-2; //i%2 wins
            if (d2==1) a[k]=22;
            continue;
          }
          a[k] = 3*i + 1 + d2;
        }
        if (d>j){
          // i%2 wins
          a[k] = (i%2) - 2;
        }
      }
      ans.pb(a);
    }
  }
  ans0[0]=0;
  FOR(i,1,N+1){
    if (i%3==0){
      ans0[i]=-1;
    }
    if (i%3==2){
      ans0[i]=-2;
    }
  }
  ans.pb(ans0);
  // i=1 to x
  FOR(i,1,13){
    vi ans1(N+1); // if bit is on
    vi ans2(N+1); // if bit is off
    ans1[0] = (i%2); ans2[0] = (i%2);
    FOR(j,1,N+1){
      if ((j&(1<<(13-i))) != 0){
        if ((j&(1<<(12-i))) != 0) ans1[j] = 2*i+1;
        else ans1[j] = 2*i+2;
        ans2[j] = (i%2) - 2; // person i%2 wins
      }else{
        ans1[j] = -1 - (i%2); // person i%2 loses
        if ((j&(1<<(12-i))) != 0) ans2[j] = 2*i+1;
        else ans2[j] = 2*i+2;
      }
    }
    ans.pb(ans1);
    ans.pb(ans2);
  }
  vi ans1(N+1), ans2(N+1);
  ans1[0]=1; ans2[0]=1;
  FOR(i,1,N+1){
    if (i%2==1){
      ans2[i]=-1;
    }else{
      ans1[i]=-2;
    }
  }
  ans.pb(ans1); ans.pb(ans2);
  return ans;
}

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