Submission #796577

#	Time	Username	Problem	Language	Result	Execution time	Memory
796577		IvanJ	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	9 ms	1468 KiB

prison

#include "prison.h"
#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int m;
vector<int> dp, opt;
vector<vector<int>> s;

void rek(int written, int lst_possible_written, int x, int lo, int hi, int lo1, int hi1, int bag) {
	s[written][0] = bag;
	for(int i = lo1;i <= lo;i++) s[written][i] = bag ? -2 : -1;
	for(int i = hi;i <= hi1;i++) s[written][i] = bag ? -1 : -2;
	if(x == 0) return;
	int l = lo + 1, r = hi - 1;
	int gap = dp[x - opt[x]], cnt = 1;
	for(int i = l;i < r;i += gap) {
		for(int j = i;j < i + gap;j++) 
			s[written][j] = lst_possible_written + cnt;
		rek(lst_possible_written + cnt, lst_possible_written + opt[x], x - opt[x], i, i + gap - 1, lo, hi, !bag);
		cnt++;
	}
}

vector<vector<int>> devise_strategy(int N) {
	dp.pb(2), opt.pb(1);
	while(dp.back() < N) {
		int x = (int)dp.size();
		dp.pb(0), opt.pb(0);
		for(int i = 1;i <= x;i++) {
			if(i * dp[x - i] + 2 > dp[x]) 
				dp[x] = i * dp[x - i] + 2, opt[x] = i;
		}
	}
	
	m = (int)dp.size();
	vector<int> v(dp.back() + 1, 0);
	for(int i = 0;i < m;i++) s.pb(v);
	rek(0, 0, m - 1, 1, dp.back(), 1, dp.back(), 0);
	for(int i = 0;i < m;i++) {
		//for(int j : s[i]) cout << j << " ";
		//cout << "\n";
		while((int)s[i].size() > N + 1) s[i].pop_back();
	}
	return s;
}

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