Submission #1050755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050755		phoenix	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	6 ms	1116 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

int get_bit(int N, int i) {
    while (i--) N /= 3;
    return N % 3;
}

vector<vector<int>> devise_strategy(int N) {
    int X = 22;
    vector<vector<int>> S(X + 1, vector<int>(N + 1, 0));
    S[0][0] = 0;
    for (int i = 1; i <= N; i++) 
        S[0][i] = 1 + get_bit(i, 7);
     
    for (int i = 1; i <= X - 1; i++) {
        int k = (i - 1) / 3;
        int pos = 7 - k;
        int a = (i - 1) % 3;
        S[i][0] = (k % 2 == 0);
        for (int j = 1; j <= N; j++) {
            int b = (get_bit(j, pos));
            if (a != b) {
                if (a < b) 
                    S[i][j] = (S[i][0] ? -1 : -2);
                else
                    S[i][j] = (S[i][0] ? -2 : -1); 
            } else {
                if (pos > 1) {
                    S[i][j] = (k + 1) * 3 + 1 + get_bit(j, pos - 1);
                }
                else {
                    if (get_bit(j, pos - 1) == 0) 
                        S[i][j] = (S[i][0] ? -2 : -1);
                    if (get_bit(j, pos - 1) == 2) 
                        S[i][j] = (S[i][0] ? -1 : -2);
                    if (get_bit(j, pos - 1) == 1)
                        S[i][j] = 22; 
                }
            }
        }
    }
    S[22][0] = 0;
    for (int i = 1; i <= N; i++) {
        int b = get_bit(i, 0);
        if (b == 0) S[22][i] = -1;
        if (b == 2) S[22][i] = -2;
        if (b == 1) S[22][i] = 0;
    }
    return S;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 70 / 90