Submission #834152

#	Time	Username	Problem	Language	Result	Execution time	Memory
834152		Trumling	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	10 ms	1100 KiB

prison

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

#define F first
#define S second
#define all(x) x.begin(),x.end()
typedef long long ll;
#define pb push_back
#define INF 9999999999999999
vector<vector<int>> devise_strategy(int N) {

vector<vector<int>>s(25,vector<int>(N+1,0));
ll now=1;
for(int i=0;i<7;i++)
now*=3;

s[0][0]=0;
for(int i=1;i<=N;i++)
if(i>=now*2)
s[0][i]=3;
else if(i>=now)
s[0][i]=2;
else
s[0][i]=1;

ll idx=1;
ll j=1;
ll count=0,nn=now;
while(now>=1)
{
s[j][0]=idx;
s[j+1][0]=idx;
s[j+2][0]=idx;
idx=(1-idx);

for(int i=1;i<=N;i++)
{
  ll curr=0;
  ll k=i,c=nn;
  for(int r=0;r<count;r++)
  {
  if(k>=c*2)
  k-=c*2;
  else if(k>=c)
  k-=c;
  c/=3;
  }

  if(k>=now*2)
  curr=3;
  else if(k>=now)
  curr=2;
  else
  curr=1;

  if(curr==3)
  {
    s[j][i]=((idx)?-2:-1);
    s[j+1][i]=((idx)?-2:-1);
    if(now!=1)
    {
    curr=0;

    if(k-now*2>=(now/3)*2)
    curr=3;
    else if(k-now*2>=(now/3))
    curr=2;
    else
    curr=1;

    switch(curr)
    {
      case 1:
      s[j+2][i]=j+3;
      break;
      case 2:
      s[j+2][i]=j+4;
      break;
      case 3:
      s[j+2][i]=j+5;
    }
    }
    continue;
  }

  if(curr==2)
  {
    s[j][i]=((idx)?-2:-1);
    s[j+2][i]=idx-2;
    if(now!=1)
    {
    curr=0;

    if(k-now>=(now/3)*2)
    curr=3;
    else if(k-now>=(now/3))
    curr=2;
    else
    curr=1;

    switch(curr)
    {
      case 1:
      s[j+1][i]=j+3;
      break;
      case 2:
      s[j+1][i]=j+4;
      break;
      case 3:
      s[j+1][i]=j+5;
    }
    }
    continue;
  }

    s[j+1][i]=idx-2;
    s[j+2][i]=idx-2;
    if(now!=1)
    {
    curr=0;

    if(k>=(now/3)*2)
    curr=3;
    else if(k>=(now/3))
    curr=2;
    else
    curr=1;

    switch(curr)
    {
      case 1:
      s[j][i]=j+3;
      break;
      case 2:
      s[j][i]=j+4;
      break;
      case 3:
      s[j][i]=j+5;
    }
    }
}
count++;
now/=3;
j+=3;
}

return s;
}

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