oj.uz

Submission #638579

# Submission time Handle Problem Language Result Execution time Memory
638579 2022-09-06T12:24:48 Z pigeonbat Prisoner Challenge (IOI22_prison) C++17
100 / 100
 14 ms 1620 KB 
#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
int group[5010][10];

void f(int s,int e,int d){
    if(s>e) return;
    group[s][d]=-1;
    group[e][d]=-2;
    if(e-s<2) return;
    if(d==6){
        int k=(e-s-1)/2;
        for(int i=0;i<k;i++) group[s+1+i][d]=d*3+1;
        for(int i=k;i<2*k;i++) group[s+1+i][d]=d*3+2;
        if((e-s-1)%2==1) group[e-1][d]=d*3+2;
        f(s+1,s+k,d+1); f(s+k+1,e-1,d+1);
        return;
    }
    int k=(e-s-1)/3;
    if((e-s-1)%3 == 0){
        for(int i=0;i<k;i++) group[s+1+i][d]=d*3+1;
        for(int i=k;i<2*k;i++) group[s+1+i][d]=d*3+2;
        for(int i=2*k;i<3*k;i++) group[s+1+i][d]=d*3+3;
        f(s+1,s+k,d+1); f(s+k+1,s+2*k,d+1); f(s+2*k+1,s+3*k,d+1);
    }
    else if((e-s-1)%3 == 1){
        for(int i=0;i<k;i++) group[s+1+i][d]=d*3+1;
        for(int i=k;i<2*k;i++) group[s+1+i][d]=d*3+2;
        for(int i=2*k;i<3*k+1;i++) group[s+1+i][d]=d*3+3;
        f(s+1,s+k,d+1); f(s+k+1,s+2*k,d+1); f(s+2*k+1,s+3*k+1,d+1);
    }
    else{
        for(int i=0;i<k;i++) group[s+1+i][d]=d*3+1;
        for(int i=k;i<2*k+1;i++) group[s+1+i][d]=d*3+2;
        for(int i=2*k+1;i<3*k+2;i++) group[s+1+i][d]=d*3+3;
        f(s+1,s+k,d+1); f(s+k+1,s+2*k+1,d+1); f(s+2*k+2,s+3*k+2,d+1);
    }
}

vector<vector<int>> re;

std::vector<std::vector<int>> devise_strategy(int N) {
    f(1, N, 0);
//    for(int t=0;t<7;t++){
//        for(int i=1;i<=N;i++) printf("%2d ",group[i][t]);
//        printf("\n");
//    }
    vector<int> tmp; tmp.push_back(0);
    for(int i=1;i<=N;i++) tmp.push_back(group[i][0]);
//    printf("\n");
//    for(int i=0;i<=N;i++) printf("%2d ",tmp[i]);
//    printf("\n");
    re.push_back(tmp);
    for(int t=1;t<=20;t++){
        tmp.clear(); tmp.resize(0);
        int tp = ((t-1)/3+1)%2;
        tmp.push_back(tp);
        for(int i=1;i<=N;i++){
            if(group[i][(t-1)/3]==-1) tmp.push_back(tp?-2:-1);
            else if(group[i][(t-1)/3]==-2) tmp.push_back(tp?-1:-2);
            else if(group[i][(t-1)/3]<t) tmp.push_back(tp?-2:-1);
            else if(group[i][(t-1)/3]>t) tmp.push_back(tp?-1:-2);
            else if(group[i][(t-1)/3+1]==-1) tmp.push_back(tp?-2:-1);
            else if(group[i][(t-1)/3+1]==-2) tmp.push_back(tp?-1:-2);
            else tmp.push_back(group[i][(t-1)/3+1]);
        }
//        for(int i=0;i<=N;i++) printf("%2d ",tmp[i]);
//        printf("\n");
        re.push_back(tmp);
    }
    return re;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 10 ms 1364 KB Output is correct
6 Correct 12 ms 1620 KB Output is correct
7 Correct 14 ms 1568 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 8 ms 1348 KB Output is correct