oj.uz

Submission #639770

# Submission time Handle Problem Language Result Execution time Memory
639770 2022-09-11T15:07:18 Z study Prisoner Challenge (IOI22_prison) C++17
100 / 100
 11 ms 1364 KB 
#include <bits/stdc++.h>
#include "prison.h"
using namespace std;

vector<vector<int>> ans;

void calc(int prev, int level, int where, int prev_l, int prev_r, int L, int R, int iter){
	int idx = (level-1)*3+where;
	if (iter%2 == 0) ans[idx][0] = 1;
	for (int i=L; i<=R; ++i) ans[prev][i] = idx;
	for (int i=prev_l; i<=L; ++i) ans[idx][i] = -ans[idx][0]-1;
	for (int i=R; i<=prev_r; ++i) ans[idx][i] = ans[idx][0]-2;
	L++; R--;
	if (L > R) return;
	if (R-L == 0){
		calc(idx,level+1,1,L-1,R+1,L,R,iter+1);
		return;
	}
	if (R-L <= 3){
		calc(idx,level+1,1,L-1,R+1,L,L+(R-L)/2,iter+1);
		calc(idx,level+1,2,L-1,R+1,R-(R-L)/2,R,iter+1);
		return;
	}
	int op = 1;
	if (0 <= (R-L)/3){
		calc(idx,level+1,op,L-1,R+1,L,L+(R-L)/3,iter+1);
		++op;
	}
	if (L+(R-L)/3+1 <= R-(R-L)/3-1){
		calc(idx,level+1,op,L-1,R+1,L+(R-L)/3+1,R-(R-L)/3-1,iter+1);
		++op;
	}
	if (0 <= (R-L)/3 and R-(R-L)/3 > L+(R-L)/3){
		calc(idx,level+1,op,L-1,R+1,R-(R-L)/3,R,iter+1);
		++op;
	}
}

vector<vector<int>> devise_strategy(int n){
	for (int i=0; i<21; ++i){
		ans.emplace_back(vector<int>(n+1));
	}
	calc(0,0,3,1,n,1,n,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 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 2 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 1 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 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 5 ms 672 KB Output is correct
5 Correct 8 ms 1200 KB Output is correct
6 Correct 11 ms 1360 KB Output is correct
7 Correct 11 ms 1364 KB Output is correct
8 Correct 1 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 4 ms 724 KB Output is correct
12 Correct 8 ms 1172 KB Output is correct