Submission #802407

#	Time	Username	Problem	Language	Result	Execution time	Memory
802407		SlavicG	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	16 ms	1116 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<std::vector<int>> devise_strategy(int N) {
    int M = 24;
    vector<vector<int>> a(M + 1, vector<int>(N + 1, 0));
    a[0][0] = 0;
    for(int j = 1; j <= N; ++j) {
        if(j >> 12 & 1) a[0][j] = 1;
        else a[0][j] = 2;
    } 
    for(int i = 1; i <= M; ++i) {
        int choice = ((i + 1) / 2) % 2; //parity 0 - A, par 1 - B
        int prev_set_bit = i % 2;
        int cur_bit = 13 - (i + 1) / 2;
        a[i][0] = choice;
        for(int j = 1; j <= N; ++j) {
            if(prev_set_bit) {
                if(j >> cur_bit & 1) {
                    if(i == 23 || i == 24) {
                        if(j >> (cur_bit - 1) & 1) {
                            a[i][j] = (choice == 0 ? -2 : -1);
                        } else {
                            a[i][j] = (choice == 0 ? -1 : -2);
                        }
                        continue;
                    }
                    if(j >> (cur_bit - 1) & 1) {
                        a[i][j] = (i + 1) / 2 * 2 + 1;
                    } else {
                        a[i][j] = (i + 1) / 2 * 2 + 2;
                    }
                } else {
                    a[i][j] = (choice == 0 ? -1 : -2);
                }
            } else {
                if(j >> cur_bit & 1) {
                    a[i][j] = (choice == 0 ? -2 : -1);
                } else {
                    if(i == 23 || i == 24) {
                        if(j >> (cur_bit - 1) & 1) {
                            a[i][j] = (choice == 0 ? -2 : -1);
                        } else {
                            a[i][j] = (choice == 0 ? -1 : -2);
                        }
                        continue;
                    }
                    if(j >> (cur_bit - 1) & 1) {
                        a[i][j] = (i + 1) / 2 * 2 + 1;
                    } else {
                        a[i][j] = (i + 1) / 2 * 2 + 2;
                    }
                }
            }
        }
    }
    return a;
}

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