제출 #626929

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
626929		I_love_Hoang_Yen	죄수들의 도전 (IOI22_prison)	C++17	80 / 100	13 ms	1080 KiB

prison

#include "bits/stdc++.h"
using namespace std;
 
int p3[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561};
 
// base 3
int get_bit(int n, int bit) {
    return (n % p3[bit + 1]) / p3[bit];
}
 
const int NBIT = 8;  // 3**8 > 5000

int encode(int b, int t) {
    if (b < 0) return 0;
    return 1 + (NBIT - b - 1) * 3 + t;
}
 
std::vector<std::vector<int>> devise_strategy(int n) {
    const int NSTATE = 23;
    std::vector<std::vector<int>> res(NSTATE, std::vector<int> (n+1, 0));

    // 0
    {
        res[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            int t = get_bit(i, NBIT - 1);
            res[0][i] = encode(NBIT - 1, t);
        }
    }

    // compare each digit in base 3
    for (int bit = NBIT - 1; bit >= 1; --bit) {
        for (int t = 0; t < 3; ++t) {
            int state = encode(bit, t);

            // 7 -> read 1
            // 6 -> read 0
            int cur = bit % 2;
            int last = 1 - cur;

            res[state][0] = cur;

            for (int i = 1; i <= n; ++i) {
                int cur_bit = get_bit(i, bit);
                if (t < cur_bit) res[state][i] = -1 - last;
                else if (t > cur_bit) res[state][i] = -1 - cur;
                else {
                    // 2 digits are equal -> we continue to next digit
                    // to improve, we read next digit of current number and store it directly
                    // (alternating 2 numbers)
                    if (bit > 1) res[state][i] = encode(bit - 1, get_bit(i, bit - 1));
                    else {
                        // for last digit, we know can already compare if it's 0 or 2
                        int bit_0 = get_bit(i, 0);
                        if (bit_0 == 2) res[state][i] = -1 - last;
                        else if (bit_0 == 0) res[state][i] = -1 - cur;
                        else res[state][i] = 22;
                    }
                }
            }
        }
    }

    // 22
    {
        // last digit of B == 1
        int cur = 0, last = 1;
        int state = 22;
        int bit = 0;

        res[22][0] = cur;
        for (int i = 1; i <= n; ++i) {
            // read current digit
            int cur_bit = get_bit(i, bit);
            if (cur_bit == 0) res[state][i] = -1 - cur;
            else if (cur_bit == 2) res[state][i] = -1 - last;
            else res[state][i] = 0;
        }
    }
 
    return res;
}

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