Submission #979316

#	Time	Username	Problem	Language	Result	Execution time	Memory
979316		12345678	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	7 ms	1112 KiB

prison

#include "prison.h"
 
#include <bits/stdc++.h>
 
using namespace std;
 
const int nx=5105, kx=21;
int di[]={3, 3, 3, 3, 3, 3, 2}, cnt, qs[kx];
vector<vector<int>> ans(kx, vector<int> (nx+1));
vector<pair<int, int>> d[kx];

void solve(int l, int r, int layer, int nextlayer, int cur)
{
    if (r==l+1) return;
    d[cur].push_back({l, r});
    l++, r--;
    int dif=(r-l+1)/di[layer], x=l;
    for (int i=0; i<di[layer]; i++) solve(x, x+dif-1, layer+1, nextlayer+di[layer], nextlayer+i), x=x+dif;
}

pair<int, int> getrange(int x, int layer)
{
    if (layer<=0) return {1, 5102};
    for (int i=1; i<=di[layer]; i++) for (auto y:d[qs[layer]+i]) if (y.first<=x&&x<=y.second) return y;
    return {-1, -1};
}

std::vector<std::vector<int>> devise_strategy(int N) {
    solve(1, 5102, 0, 1, 0);
    ans[0][1]=-1;
    ans[0][5102]=-2;
    ans[1][0]=ans[2][0]=ans[3][0]=1;
    for (int i=2; i<=5101; i++) ans[0][i]=(i-2)/1700+1;
    for (int i=1; i<=5102; i++)
    {
        if (i<=2) ans[1][i]=-2;
        else if (i<1701) ans[1][i]=(i-2)/566+4;
        else ans[1][i]=-1;
        if (i<=1702) ans[2][i]=-2;
        else if (i<3401) ans[2][i]=(i-1702)/566+4;
        else ans[2][i]=-1;
        if (i<=3402) ans[3][i]=-2;
        else if (i<5101) ans[3][i]=(i-3402)/566+4;
        else ans[3][i]=-1;
    }
    for (int i=1; i<=7; i++) qs[i]=qs[i-1]+di[i-1];
    for (int i=1; i<7; i++)
    {
        for (int j=1; j<=di[i]; j++)
        {
            //printf("here %d %d\n", i, j);
            ans[qs[i]+j][0]=1-(i%2);
            for (int k=1; k<=5102; k++)
            {
                //printf("herek %d\n", k);
                pair<int, int> x=getrange(k, i-2);
                if (x.first==-1||x.first==k||k==x.second) continue;
                //if (qs[i]+j==16&&k==11) cout<<"prev "<<x.first<<' '<<x.second<<'\n'; 
                x.first++;
                x.second--;
                //if ((nr.second-nr.first+1)%di[i]!=0&&++cnt<=20) cout<<"dividefirst "<<' '<<qs[i]+j<<' '<<k<<' '<<nr.first<<' '<<nr.second<<'\n';
                int dif=(x.second-x.first+1)/di[i-1];
                pair<int, int> nr;
                for (int m=1; m<=di[i-1]; m++)
                {
                    if (x.first<=k&&k<=x.first+dif-1) nr={x.first, x.first+dif-1};
                    x.first+=dif;
                }
                //if (qs[i]+j==16&&k==11) cout<<"firstrange "<<nr.first<<' '<<nr.second<<'\n'; 
                nr.first++;
                nr.second--;
                int dif2=(nr.second-nr.first+1)/di[i];
                if ((nr.second-nr.first+1)%di[i]!=0&&++cnt<=20) cout<<"divide "<<' '<<qs[i]+j<<' '<<k<<' '<<nr.first<<' '<<nr.second<<'\n';
                nr.first=nr.first+dif2*(j-1);
                nr.second=nr.first+dif2-1;
                //if (qs[i]+j==16&&k==11) cout<<"secondrange "<<nr.first<<' '<<nr.second<<'\n'; 
                if (k<=nr.first) ans[qs[i]+j][k]=(i%2)?-1:-2;
                else if (k>=nr.second) ans[qs[i]+j][k]=(i%2)?-2:-1;
                else
                {
                    nr.first++;
                    nr.second--;
                    int sz=(nr.second-nr.first+1)/di[i+1];
                    ans[qs[i]+j][k]=((k-(nr.first))/sz+1)+qs[i+1];
                }
                if (ans[qs[i]+j][k]>=kx&&cnt++<=10) cout<<"failed "<<i<<' '<<qs[i]+j<<' '<<k<<' '<<ans[qs[i]+j][k]<<'\n';
                //if (k<=50&&qs[i]+j==7) cout<<"debug "<<qs[i]+j<<' '<<k<<' '<<ans[qs[i]+j][k]<<'\n';
            }
        }
    }
    vector<vector<int>> res(kx, vector<int> (N+1));
    for (int i=0; i<kx; i++) for (int j=0; j<=N; j++) res[i][j]=ans[i][j];
    return res;
}

// 5102
// {3, 3, 3, 3, 3, 3, 2}
/*
2 1701, 1702 3401, 3402 5101
*/

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