oj.uz

Submission #828256

# Submission time Handle Problem Language Result Execution time Memory
828256 2023-08-17T07:23:08 Z ttamx Prisoner Challenge (IOI22_prison) C++17
80 / 100
 10 ms 1100 KB 
#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

const int N=5005;

int n;

vector<vector<int>> devise_strategy(int _n){
	n=_n;
	int x=29;
	vector<int> pw(8);
	pw[0]=1;
	for(int i=1;i<9;i++)pw[i]=pw[i-1]*3;
	vector<vector<int>> s(x+1,vector<int>(n+1));
	int id=0;
	s[id][0]=0;
	for(int j=1;j<=n;j++){
		int val=j/pw[7]%3;
		s[id][j]=id+val+1;
	}
	id++;
	for(int i=7;i>=1;i--){
		int c=i&1;
		for(int x=0;x<3;x++){
			s[id][0]=c;
			for(int j=1;j<=n;j++){
				int val=j/pw[i]%3;
				if(val==x){
					int val2=j/pw[i-1]%3;
					s[id][j]=id+3-x+val2;
					if(i==1){
						if(val2==0)s[id][j]=-2;
						if(val2==2)s[id][j]=-1;
						if(val2==1)s[id][j]=id+3-x;
					}
				}else if(val>x){
					s[id][j]=c-2;
				}else{
					s[id][j]=-c-1;
				}
			}
			id++;
		}
	}
	s[id][0]=0;
	for(int j=1;j<=n;j++){
		int val=j%3;
		if(val==0){
			s[id][j]=-1;
		}else{
			s[id][j]=-2;
		}
	}
	s.resize(id+1);
	return s;
}

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 1 ms 288 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 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 372 KB Output is correct
7 Correct 0 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
70.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Partially correct 0 ms 212 KB Output is partially correct
3 Partially correct 0 ms 212 KB Output is partially correct
4 Partially correct 4 ms 596 KB Output is partially correct
5 Partially correct 10 ms 980 KB Output is partially correct
6 Partially correct 9 ms 1100 KB Output is partially correct
7 Partially correct 9 ms 1100 KB Output is partially correct
8 Partially correct 0 ms 212 KB Output is partially correct
9 Partially correct 1 ms 340 KB Output is partially correct
10 Partially correct 2 ms 340 KB Output is partially correct
11 Partially correct 4 ms 652 KB Output is partially correct
12 Partially correct 8 ms 1044 KB Output is partially correct