Submission #697835

#	Time	Username	Problem	Language	Result	Execution time	Memory
697835		firewater	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	14 ms	3360 KiB

prison

#include "prison.h"
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 5050
using namespace std;
vector<vector<int> >d(21);
int l,r,x,g,gg,m,now,num,Num,L,R,a[30][N],sL[30][N],sR[30][N],sNum[30][N];

vector<vector<int> > devise_strategy(int M) {
	for(int i=1;i<=5000;++i){
	    sL[0][i]=0;
	    sR[0][i]=5001;
	    sNum[0][i]=5010;
	}
    now=0;
    
    for(int i=1;i<=6;++i){
        x=i&1;
        m=(i==1?1:3);
        for(int j=0;j<m;++j){
        	a[now][0]=x;
            for(int k=1;k<=M;++k){
	            L=sL[now][k];
	            R=sR[now][k];
	            Num=sNum[now][k];
	            
	            if(k==L||k==R){
	            	l=L;
	            	r=R;
	            	num=Num;
				}
				else{
	            	L++;R--;
	                g=(k-L)/Num;
		        	l=L+Num*g;
		        	r=min(R,L+Num*(g+1)-1);
		        	L--;R++;
		        	
		        	if(k!=l&&k!=r){
		        		l++;r--;
			        	num=(r-l+1+2)/3;
		                gg=(k-l)/num;
		                l--;r++;
		        	}
				}
	        	
                for(int kk=0;kk<3;++kk){
                	sL[now+m-j+kk][k]=l;
                	sR[now+m-j+kk][k]=r;
					sNum[now+m-j+kk][k]=num;
				}
                if(k==L)a[now][k]=-1-x;
                else if(k==R)a[now][k]=-1-(x^1);
                else if(g>j)a[now][k]=-1-(x^1);
                else if(g<j)a[now][k]=-1-x;
                else{
                    if(k==l)a[now][k]=-1-x;
                    else if(k==r)a[now][k]=-1-(x^1);
                    else a[now][k]=now+m-j+gg;
                }
            }
            now++;
        }
    }
    for(int i=7;i<=8;++i){
        x=i&1;
        m=(i==7?3:2);
        for(int j=0;j<m;++j){
        	a[now][0]=x;
            for(int k=1;k<=M;++k){
	            L=sL[now][k];
	            R=sR[now][k];
	            Num=sNum[now][k];
	            
	            if(k==L||k==R){
	            	l=L;
	            	r=R;
	            	num=Num;
				}
				else{
	            	L++;R--;
	                g=(k-L)/Num;
		        	l=L+Num*g;
		        	r=min(R,L+Num*(g+1)-1);
		        	L--;R++;
		        	
		        	if(k!=l&&k!=r){
		        		l++;r--;
			        	num=(r-l+1+1)/2;
		                gg=(k-l)/num;
		                l--;r++;
		        	}
				}
	        	
                for(int kk=0;kk<3;++kk){
                	sL[now+m-j+kk][k]=l;
                	sR[now+m-j+kk][k]=r;
					sNum[now+m-j+kk][k]=num;
				}
                if(k==L)a[now][k]=-1-x;
                else if(k==R)a[now][k]=-1-(x^1);
                else if(g>j)a[now][k]=-1-(x^1);
                else if(g<j)a[now][k]=-1-x;
                else{
                    if(k==l)a[now][k]=-1-x;
                    else if(k==r)a[now][k]=-1-(x^1);
                    else a[now][k]=now+m-j+gg;
                    if(a[now][k]==21){
                    	M++;M--;
					}
                }
            }
            now++;
        }
    }
    for(int i=0;i<=20;++i)
    	for(int j=0;j<=M;++j)
			d[i].push_back(a[i][j]);
  return d;
}

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