oj.uz

Submission #748734

# Submission time Handle Problem Language Result Execution time Memory
748734 2023-05-26T19:53:18 Z QwertyPi Prisoner Challenge (IOI22_prison) C++17
100 / 100
 11 ms 1364 KB 
#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> ans;

const int MAX = 21;
const int C = 7; 
int a[C] = {2, 3, 3, 3, 3, 3, 3};
int p[C] = {18, 15, 12, 9, 6, 3, 0};

void solve(int L, int R, int ai, int ID){
	ans[ID][0] = ai % 2 != 0;
	
	if(R - L < 2) return;
	ans[ID][L] = ai % 2 != 0 ? -2 : -1;
	ans[ID][R - 1] = ai % 2 != 0 ? -1 : -2;
	L++; R--;
	if(L >= R) return;
	
	assert(ai != -1);
	
	vector<int> M;
	M.push_back(L);
	for(int i = 1; i < a[ai]; i++){
		M.push_back((L * (a[ai] - i) + R * i) / a[ai]);
	}
	M.push_back(R);
	
	for(int i = 0; i < a[ai]; i++){
		for(int j = M[i]; j < M[i + 1]; j++){
			ans[ID][j] = p[ai] + i + 1;
		}
	}
	for(int i = 0; i < a[ai]; i++){
		for(int j = L - 1; j <= M[i]; j++){
			ans[p[ai] + i + 1][j] = ai % 2 != 0 ? -1 : -2;
		}
		solve(M[i], M[i + 1], ai - 1, p[ai] + i + 1);
		for(int j = M[i + 1]; j < R + 1; j++){
			ans[p[ai] + i + 1][j] = ai % 2 != 0 ? -2 : -1;
		}
	}
}

vector<vector<int>> devise_strategy(int N) {
	ans = vector<vector<int>>(MAX, vector<int>(N + 1));
	solve(1, N + 1, C - 1, 0);
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 400 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 5 ms 780 KB Output is correct
5 Correct 9 ms 1108 KB Output is correct
6 Correct 11 ms 1320 KB Output is correct
7 Correct 10 ms 1364 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 5 ms 724 KB Output is correct
12 Correct 9 ms 1100 KB Output is correct