Submission #756519

#	Time	Username	Problem	Language	Result	Execution time	Memory
756519		definitelynotmee	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	11 ms	1064 KiB

prison

#include<bits/stdc++.h>
#include"prison.h"
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
using namespace std;
template <typename T>
using bstring = basic_string<T>;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 998244353;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
const int MAXN = 1e6+1;

std::vector<std::vector<int>> devise_strategy(int N) {

    vector<pii> dp(26);
    dp[0] = {2,1};

    for(int i = 1; i < 26; i++){
        for(int j = 1; j <= i; j++){
            dp[i] = max(dp[i],{dp[i-j].ff*j+2,j});
        }

        // << "dp[" << i << "] = " << dp[i].ff << ' ' << dp[i].ss << '\n';
    }
    // << "==============================\n";
    int start = dp[20].ff;

    matrix<int> resp(21,vector<int>(start+1));

    reverse(dp.begin(), dp.begin()+21);

    int change = 0;
    int cur = 0;

    for(int i = 0; i <= 20; i++){
        resp[i][0] = cur;
        if(!change)
            change = dp[i].ss, cur^=1;
        change--;
    }

    int x = 0;

    auto solve =[&](int k, int nextk, int l, int r, int lastl, int lastr, auto solve) -> void {
        // << k << ' ' << nextk << ' ' << l << ' ' << r << ' ' << lastl << ' ' << lastr << endl;
        // << dp[nextk].ff << ' ' << dp[nextk].ss << '\n';
        if(k == 21)
            return;
        for(int i = l; i <= lastl; i++){
            resp[k][i] = -resp[k][0]-1;
        }
        for(int i = lastr; i <= r; i++){
            resp[k][i] = -(resp[k][0]^1)-1;
        }
        l = max(lastl+1,l), r = min(lastr-1,r);

        int sz = r-l+1;
        int jmp = sz/dp[nextk].ss;
        // << l << ' ' << r << "->" << sz << ' ' << jmp << ' ' <<sz%dp[nextk].ss << '\n';
        int nextkfrfr = nextk+dp[nextk].ss;

        
        for(int block = 0; block < dp[nextk].ss; block++){
            int nextl = l+jmp*block, nextr = l+jmp*(block+1)-1;
            for(int i = nextl; i <= nextr; i++){
                resp[k][i] = nextk+block+1;
            }
            solve(nextk+block+1, nextkfrfr, lastl, lastr, nextl, nextr, solve);
        }

    };
    solve(0,0, 1, start, 1, start, solve);

    for(int i = 0; i < 21; i++){
        while(resp[i].size() > N+1)
            resp[i].pop_back();
    }

    return resp;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:85:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |         while(resp[i].size() > N+1)
      |               ~~~~~~~~~~~~~~~^~~~~
prison.cpp:52:9: warning: unused variable 'x' [-Wunused-variable]
   52 |     int x = 0;
      |         ^

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