oj.uz

Submission #979460

# Submission time Handle Problem Language Result Execution time Memory
979460 2024-05-11T04:30:46 Z 12345678 Prisoner Challenge (IOI22_prison) C++17
100 / 100
 9 ms 1372 KB 
#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)
{
    d[cur].push_back({l, r});
    if (r==l+1) return;
    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;
}

std::vector<std::vector<int>> devise_strategy(int N) {
    solve(1, 5102, 0, 1, 0);
    ans[0][1]=-1;
    ans[0][5102]=-2;
    for (int i=2; i<=5101; i++) ans[0][i]=(i-2)/1700+1;
    for (int i=1; i<=7; i++) qs[i]=qs[i-1]+di[i-1];
    for (int i=0; i<7; i++)
    {
        for (int j=1; j<=di[i]; j++)
        {
            ans[qs[i]+j][0]=1-(i%2);
            for (auto x:d[qs[i]+j])
            {
                ans[qs[i]+j][x.first]=(i%2)?-1:-2;
                ans[qs[i]+j][x.second]=(i%2)?-2:-1;
                if (x.first+1==x.second) continue;
                int sz=(x.second-x.first-1)/di[i+1];
                for (int k=x.first+1; k<x.second; k++) ans[qs[i]+j][k]=((k-x.first-1)/sz)+1+qs[i+1];
            }
            if (i==0)
            {
                for (int k=1; ; k++) 
                {
                    if (ans[qs[i]+j][k]) break;
                    ans[qs[i]+j][k]=(i%2)?-1:-2;
                }
                for (int k=5102; ; k--) 
                {
                    if (ans[qs[i]+j][k]) break;
                    ans[qs[i]+j][k]=(i%2)?-2:-1; 
                }
            }
            else
            {
                for (int m=1; m<=di[i-1]; m++)
                {
                    for (auto r:d[qs[i-1]+m])
                    {
                        int vl=(i%2)?-1:-2;
                        for (int k=r.first; k<=r.second; k++)
                        {
                            if (ans[qs[i]+j][k]) vl=(i%2)?-2:-1;
                            else ans[qs[i]+j][k]=vl;
                        }
                    }
                }
            }
        }
    }
    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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 912 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct
6 Correct 9 ms 1368 KB Output is correct
7 Correct 9 ms 1372 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 916 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 5 ms 1116 KB Output is correct
12 Correct 7 ms 1372 KB Output is correct