Submission #1056396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056396		vjudge1	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	6 ms	1316 KiB

prison

#include "prison.h"

#include <vector>
using namespace std;
vector<int>layer{3,3,3,3,3,3,2};
int blkin[5010][10],whichone[50],sum[50];
vector<int> which_to_do(int num,int n){
    vector<int>res(n+1);
    res[0]=whichone[num]&1;
    int X=whichone[num];
    int Y=num-sum[X-1];
    if(!num){
        for(int i=1;i<=n;i++)
            res[i]=blkin[i][X];
    } else {
        for(int i=1;i<=n;i++) {
            if(!blkin[i][X-1])continue;
            if(blkin[i][X-1]<0)
                res[i]=-(-blkin[i][X-1]-1^1)-1;
            else if(blkin[i][X-1]!=Y)
                res[i]=-((blkin[i][X-1]>Y)^res[0])-1;
            else if(blkin[i][X]<0)
                res[i]=blkin[i][X];
            else res[i]=blkin[i][X]+sum[X];
        }
    }
    return res;
}
void build_blocks(int l,int r,int I){
    blkin[l][I]=-(I&1)-1;
    blkin[r][I]=-!(I&1)-1;
    int sz=r-l-1;
    if(!sz)return;
    if(layer[I]==3) {
        int sz1=sz/3,sz2=sz1,sz3=sz1;
        if(sz1+sz2+sz3<sz)
            sz1++;
        if(sz1+sz2+sz3<sz)
            sz2++;
        for(int i=1;i<=sz1;i++)
            blkin[l+i][I]=1;
        for(int i=1;i<=sz2;i++)
            blkin[l+i+sz1][I]=2;
        for(int i=1;i<=sz3;i++)
            blkin[l+i+sz1+sz2][I]=3;
        build_blocks(l+1,l+sz1,I+1);
        build_blocks(l+sz1+1,l+sz1+sz2,I+1);
        build_blocks(l+sz1+sz2+1,l+sz1+sz2+sz3,I+1);
    } else {
        blkin[l+1][I]=1;
        blkin[l+2][I]=1;
        blkin[l+3][I]=2;
        blkin[l+4][I]=2;
        build_blocks(l+1,l+2,I+1);
        build_blocks(l+3,l+4,I+1);
    }
}
vector<vector<int>> devise_strategy(int N) {
    for(int i=1;i<8;i++)
        sum[i]=sum[i-1]+layer[i-1];
    for(int i=1;i<=20;i++)
        whichone[i]=(i>sum[whichone[i-1]])+whichone[i-1];
    build_blocks(1,5000,0);
    vector<vector<int>> ans;
    for(int i=0;i<=20;i++)
        ans.push_back(which_to_do(i,N));
    return ans;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<int> which_to_do(int, int)':
prison.cpp:19:40: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   19 |                 res[i]=-(-blkin[i][X-1]-1^1)-1;
      |                          ~~~~~~~~~~~~~~^~

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