Submission #1008489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008489		birktj	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	9 ms	1564 KiB

prison

#include <vector>
#include <iostream>
#include "prison.h"

using namespace std;

vector<vector<int>> strategy;

// void solve(int step, int inner_min, int inner_max, int outer_min, int outer_max) {
//     // cerr << step << endl;
//     // cerr << "a_min " << a_min << " a_max " << a_max << endl;
//     // cerr << "b_min " << b_min << " b_max " << b_max << endl;
//     if (step > 23) {
//         return;
//     }
//     // if (a_min >= a_max) {
//     //     return;
//     // }
//     // if (b_min >= b_max) {
//     //     return;
//     // }
//     int inner_mid = (inner_min + inner_max) / 2;
//     int outer_mid = (outer_min + outer_max) / 2;

//     int pile = step % 2;

//     for (int i = inner_min; i <= inner_max; i++) {
//         if (i < b_min) {
//             // b is bigger
//             strategy[step][i] = -2;
//         } else if (i > b_max) {
//             // b is smaller 
//             strategy[step][i] = -1;
//         } else if (i <= inner_mid) {
//             strategy[step][i] = step+1;
//         } else {
//             strategy[step][i] = step+3;
//         }
//     }
//     solve(step+1, inner_min, inner_mid, inner_min, inner_max);
//     solve(step+1, inner_mid+1, inner_max, inner_min, inner_max);
// }

void solve(int step, int a_min, int a_max, int b_min, int b_max) {
    // cerr << step << endl;
    // cerr << "a_min " << a_min << " a_max " << a_max << endl;
    // cerr << "b_min " << b_min << " b_max " << b_max << endl;
    if (step > 50) {
        return;
    }
    // if (a_min >= a_max) {
    //     return;
    // }
    // if (b_min >= b_max) {
    //     return;
    // }
    int a_mid = (a_min + a_max) / 2;
    int b_mid = (b_min + b_max) / 2;

    int inner_min = max(a_min, b_min);
    int inner_max = min(a_max, b_max);
    int inner_mid = (inner_min + inner_max) / 2;
    
    if (step % 2 == 0) {
        // Looking in pile a
        for (int i = a_min; i <= a_max; i++) {
            if (i < b_min) {
                // b is bigger
                strategy[step][i] = -1;
            } else if (i > b_max) {
                // b is smaller 
                strategy[step][i] = -2;
            } else if (i <= inner_mid) {
                // Overlapping range
                strategy[step][i] = step+1;
            } else {
                strategy[step][i] = step+3;
            }
        }
        if (inner_min < inner_max) {
            solve(step+3, inner_mid+1, inner_max, b_min, b_max);
            solve(step+1, inner_min, inner_mid, b_min, b_max);
        }
    } else {
        // Looking in pile b       
        for (int i = b_min; i <= b_max; i++) {
            if (i < a_min) {
                // a is bigger
                strategy[step][i] = -2;
            } else if (i > a_max) {
                // a is smaller 
                strategy[step][i] = -1;
            } else if (i <= inner_mid) {
                // Overlapping range
                strategy[step][i] = step+1;
            } else {
                strategy[step][i] = step+3;
            }
        }
        if (inner_min < inner_max) {
            solve(step+3, a_min, a_max, inner_mid+1, inner_max);
            solve(step+1, a_min, a_max, inner_min, inner_mid);
        }
    }
}

vector<vector<int>> devise_strategy(int n) {
    strategy = vector<vector<int>>(60, vector<int>(n+1, 0));
    for (int i = 0; i < 60; i++) {
        strategy[i][0] = i % 2;
    }
    solve(0, 1, n, 1, n);
    // cerr << "completed" << endl;
    // for (int i = 0; i < 30; i++) {
    //     for (int j = 0; j < n; j++)
    //         cerr << strategy[i][j] << " ";
    //     cerr << endl;
    // }
    return strategy;
}

Compilation message (stderr)

prison.cpp: In function 'void solve(int, int, int, int, int)':
prison.cpp:57:9: warning: unused variable 'a_mid' [-Wunused-variable]
   57 |     int a_mid = (a_min + a_max) / 2;
      |         ^~~~~
prison.cpp:58:9: warning: unused variable 'b_mid' [-Wunused-variable]
   58 |     int b_mid = (b_min + b_max) / 2;
      |         ^~~~~

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