oj.uz

Submission #756519

# Submission time Handle Problem Language Result Execution time Memory
756519 2023-06-11T19:22:03 Z definitelynotmee Prisoner Challenge (IOI22_prison) C++17
100 / 100
 11 ms 1064 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 684 KB Output is correct
5 Correct 2 ms 800 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 684 KB Output is correct
8 Correct 2 ms 680 KB Output is correct
9 Correct 2 ms 684 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 812 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 2 ms 684 KB Output is correct
9 Correct 2 ms 724 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 680 KB Output is correct
2 Correct 1 ms 684 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 8 ms 1016 KB Output is correct
6 Correct 11 ms 980 KB Output is correct
7 Correct 11 ms 1064 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 5 ms 852 KB Output is correct
12 Correct 8 ms 940 KB Output is correct