oj.uz

Submission #685404

# Submission time Handle Problem Language Result Execution time Memory
685404 2023-01-24T10:09:33 Z 79brue Prisoner Challenge (IOI22_prison) C++17
100 / 100
 13 ms 980 KB 
#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

int grp[] = {0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7};
int off[] = {0, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2};
int seq[] = {3, 3, 3, 3, 3, 3, 2};
int lim[] = {5102, 1700, 566, 188, 62, 20, 6, 2, 1};
int stt[] = {0, 1, 4, 7, 10, 13, 16, 19};

vector<vector<int> > devise_strategy(int N){
    n = N;
    vector<vector<int> > ret (21);
    for(int c=0; c<=20; c++){
        ret[c].resize(N+1);
        int g = grp[c];
        ret[c][0] = g%2;
        for(int i=1; i<=N; i++){
            if(i == 1702){
                printf("");
            }
            int v = i;
            bool bad = 0;
            for(int j=0; j<g; j++){
                if(v == 1 || v == lim[j]){
                    if(v == 1) ret[c][i] = (g%2) ? -2 : -1, bad = 1;
                    else       ret[c][i] = (g%2) ? -1 : -2, bad = 1;
                    break;
                }
                if(j == g-1 && (v-2)/lim[j+1]+1 != off[c]){
                    if((v-2)/lim[j+1]+1 < off[c]) ret[c][i] = (g%2) ? -2 : -1, bad = 1;
                    else                          ret[c][i] = (g%2) ? -1 : -2, bad = 1;
                    break;
                }
                v = (v - 2) % lim[j+1] + 1;
            }
            if(bad) continue;
            /// 가능한 답안인 경우
            if(v == 1) ret[c][i] = (g%2) ? -2 : -1;
            else if(v == lim[g]) ret[c][i] = (g%2) ? -1 : -2;
            else if(g==7) ret[c][i] = 0; /// 있을 수 없는 경우
            else if(g==0) ret[c][i] = (v-2)/lim[g+1]+1;
            else{ /// 끝점 아님
                int tv = (v-2)/lim[g]+1;
                if(!g) ret[c][i] = tv;
                else ret[c][i] = stt[g+1] + (v-2)/lim[g+1];
            }
        }
    }
    return ret;
}

Compilation message

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:25:24: warning: zero-length gnu_printf format string [-Wformat-zero-length]
   25 |                 printf("");
      |                        ^~

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 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 340 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 6 ms 596 KB Output is correct
5 Correct 11 ms 852 KB Output is correct
6 Correct 12 ms 980 KB Output is correct
7 Correct 13 ms 912 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Correct 10 ms 772 KB Output is correct