oj.uz

Submission #1077235

# Submission time Handle Problem Language Result Execution time Memory
1077235 2024-08-27T03:45:17 Z pcc Prisoner Challenge (IOI22_prison) C++17
36.5 / 100
 447 ms 3536 KB 
#include "prison.h"

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

std::vector<std::vector<int>> devise_strategy(int N) {
	int ans = 13*2*2;//nowbit,turn,bit of a
	vector<vector<int>> re(ans,vector<int>(N+1,-1));
	vector<int> all;
	for(int i = 0;i<ans;i++){
		int turn = ((i>>1)&1);
		int tar = 12-(i>>2);
		int bit = i&1;
		if(turn == 0)re[i][0] = 0;
		else re[i][0] = 1;
		for(int j = 1;j<=N;j++){
			if(turn == 0){
				re[i][j] = (i/4*4)|2|((j>>tar)&1);
			}
			else{
				if(bit != ((j>>tar)&1)){
					if((j>>tar)&1)re[i][j] = -1;
					else re[i][j] = -2;
				}
				else{
					re[i][j] = ((i/4+1)*4);
					if(re[i][j]>=ans)re[i][j] = -1;
				}
			}
		}
	}
	for(auto &i:re)for(auto &j:i)if(j>=0)all.push_back(j);
	all.push_back(0);
	sort(all.begin(),all.end());all.resize(unique(all.begin(),all.end())-all.begin());cerr<<"ALL: "<<all.size()<<endl;
	ans = all.size();
	vector<vector<int>> v(ans,vector<int>(N+1,-1));
	for(int i = 0;i<ans;i++){
		int p = all[i];
		v[i][0] = re[p][0];
		for(int j = 1;j<=N;j++){
			if(re[p][j]<0)v[i][j] = re[p][j];
			else v[i][j] = lower_bound(all.begin(),all.end(),re[p][j])-all.begin();
		}
	}
	for(int i = 0;i<ans;i++){
		cerr<<i<<":";for(auto &j:v[i])cerr<<j<<',';cerr<<endl;
	}
	cerr<<"INIT DONE!"<<endl;
	return v;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 18 ms 596 KB Output is correct
4 Correct 19 ms 604 KB Output is correct
5 Correct 37 ms 604 KB Output is correct
6 Correct 38 ms 600 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 28 ms 652 KB Output is correct
9 Correct 30 ms 600 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 18 ms 604 KB Output is correct
4 Correct 20 ms 604 KB Output is correct
5 Correct 37 ms 772 KB Output is correct
6 Correct 37 ms 600 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 10 ms 528 KB Output is correct
9 Correct 34 ms 756 KB Output is correct

Subtask #3
26.5 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Partially correct 1 ms 348 KB Output is partially correct
3 Partially correct 1 ms 344 KB Output is partially correct
4 Partially correct 192 ms 1740 KB Output is partially correct
5 Partially correct 332 ms 2844 KB Output is partially correct
6 Partially correct 411 ms 3536 KB Output is partially correct
7 Partially correct 447 ms 3376 KB Output is partially correct
8 Partially correct 2 ms 344 KB Output is partially correct
9 Partially correct 32 ms 660 KB Output is partially correct
10 Partially correct 50 ms 860 KB Output is partially correct
11 Partially correct 155 ms 1496 KB Output is partially correct
12 Partially correct 326 ms 2784 KB Output is partially correct