oj.uz

Submission #1011646

# Submission time Handle Problem Language Result Execution time Memory
1011646 2024-07-01T02:54:17 Z bachhoangxuan Prisoner Challenge (IOI22_prison) C++17
100 / 100
 6 ms 1116 KB 
#include "prison.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> devise_strategy(int N) {
    vector<vector<int>> s(21,vector<int>(N+1,0));
    auto dnc = [&](auto &&dnc,int l,int r,int L,int R,int t,int id,int sz){
        if(l>r) return;
        l++;r--;
        s[id][0]=t;
        for(int i=L;i<=R;i++) if(i<l || r<i) s[id][i]=-((r<i)^t)-1;
        int S=r-l+1,k=min(S,2+(S>4)),d=ceil(1.0*S/k);
        for(int x=l,i=1;i<=k;i++){
            int y=min(r,x+d-1);
            for(int j=x;j<=y;j++) s[id][j]=sz+i;
            dnc(dnc,x,y,l-1,r+1,t^1,sz+i,sz+k);
            x=y+1;
        }
    };
    dnc(dnc,1,N,1,N,0,0,0);
    return s;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 420 KB Output is correct
4 Correct 3 ms 736 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 6 ms 1112 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 5 ms 976 KB Output is correct