oj.uz

Submission #626988

# Submission time Handle Problem Language Result Execution time Memory
626988 2022-08-12T04:13:47 Z timmyfeng Prisoner Challenge (IOI22_prison) C++17
100 / 100
 17 ms 1040 KB 
#include "prison.h"

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> devise_strategy(int n) {
	const int M = 20, N = 5102;

	int xl = 0, xr = 1;
	vector strat(M + 1, vector<int>(N));
	vector<int> mapping(N), div = {3, 3, 3, 3, 3, 3, 2, 0};
	for (int k = 0; k < (int) div.size(); ++k) {
		for (int l = 0, r = 0; l < N; l = r) {
			while (r < N && mapping[r] == mapping[l]) ++r;
			for (int x = xl; x < xr; ++x) {
				if (mapping[l] < x) {
					fill(strat[x].begin() + l, strat[x].begin() + r, -1);
				} else if (mapping[l] > x) {
					fill(strat[x].begin() + l, strat[x].begin() + r, INT_MAX);
				} else {
					strat[x][l] = -1, strat[x][r - 1] = INT_MAX;
					for (int i = l + 1; i < r - 1; ++i) {
						strat[x][i] = xr + div[k] * (i - l - 1) / (r - l - 2);
					}
				}
			}
		}
		for (int i = 0; i < N; ++i) {
			if (xl <= mapping[i] && mapping[i] < xr) {
				mapping[i] = strat[mapping[i]][i];
			}
		}
		for (int x = xl; x < xr; ++x) {
			strat[x].resize(n);
			for (auto &y : strat[x]) if (y == INT_MAX) y = -2;
			strat[x].insert(strat[x].begin(), k % 2);
			if (k % 2) for (auto &y : strat[x]) if (y < 0) y = -3 - y;
		}
		xl = xr, xr += div[k];
	}
	return strat;
}

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 1 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 2 ms 724 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 2 ms 724 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 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 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 8 ms 852 KB Output is correct
5 Correct 10 ms 980 KB Output is correct
6 Correct 17 ms 1040 KB Output is correct
7 Correct 11 ms 1000 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 5 ms 852 KB Output is correct
12 Correct 15 ms 956 KB Output is correct