oj.uz

Submission #1043762

# Submission time Handle Problem Language Result Execution time Memory
1043762 2024-08-04T16:37:21 Z Marco_Escandon Prisoner Challenge (IOI22_prison) C++17
90 / 100
 7 ms 1768 KB 
#include<bits/stdc++.h>
using namespace std;
//#include "prison.h"
typedef int ll;
vector<vector<ll>> s;
ll cad[]={ 3, 3, 3, 3, 3, 2, 2, 1, 2};
ll P[22][5588]={ };
void sol(ll p,ll a, ll b)
{
    if(a>=b) return;
    P[p][a]=-1e9;
    P[p][b]=1e9;
    if(a+1==b) return;
    ll t1=(b-a-1)/cad[p];
    ll t2=(b-a-1)%cad[p];
    ll c=0;
    for(int i=a+1; i<b;c++)
    {
        for(int j=0;j<t1+t2; j++)
        {
            P[p][i+j]=c;
        }
        sol(p+1,i,i+t1+t2-1);
        i=i+t1+t2;
        t2--;t2=max(t2,0);
    }
}
ll Hash(ll p, ll vp) { return vp*8+p; }
std::vector<std::vector<int>> devise_strategy(int n) {
    sol(0,1,5588);
    s.assign(22,vector<ll>(n+1,0));
    s[0][0]=0;s[0][1]=-1;s[0][n]=-2;
    for(int i=2; i<n; i++)
        s[0][i]=Hash(0,P[0][i])+1;
    for(int i=1; i<22; i++)
    {
        ll temp=i-1;
        ll va=temp%8;
        temp/=8;
        swap(va,temp);
        s[i][0]=max(((temp+1)%2),0);
        for(int j=1; j<=n; j++)
        {
            ll vp=P[temp][j];
            if(va==vp)s[i][j]=Hash(temp+1,P[temp+1][j])+1;
            else if((s[i][0]==0&&vp<va)||(s[i][0]==1&&vp>va)) s[i][j]=-1;
            else s[i][j]=-2;
            if(va==vp&&P[temp+1][j]>=22) s[i][j]=-2+s[i][0];
            else if(va==vp&&P[temp+1][j]<-1e7) s[i][j]=-1-s[i][0];
        }
    }
    /*for(int i=1; i<22; i++)
    {
        cout<<s[i][0]<<"      ";
        ll temp=i-1;
        ll va=temp%8;
        temp/=8;
        swap(va,temp);
        cout<<temp<<va<<P[temp][220]<<" ";
        //for(int j=1; j<=4; j++)
        {
            cout<<s[i][4]<<P[(i-1)%8][4]<<" "<<s[i][220]<<P[(i-1)%8][220]<<" ";;
        }
        cout<<"\n";
    }*/
    return s;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
80.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Partially correct 0 ms 604 KB Output is partially correct
3 Partially correct 0 ms 604 KB Output is partially correct
4 Partially correct 3 ms 1116 KB Output is partially correct
5 Partially correct 5 ms 1372 KB Output is partially correct
6 Partially correct 7 ms 1624 KB Output is partially correct
7 Partially correct 6 ms 1768 KB Output is partially correct
8 Partially correct 0 ms 604 KB Output is partially correct
9 Partially correct 1 ms 604 KB Output is partially correct
10 Partially correct 1 ms 604 KB Output is partially correct
11 Partially correct 3 ms 896 KB Output is partially correct
12 Partially correct 5 ms 1520 KB Output is partially correct