oj.uz

Submission #954394

# Submission time Handle Problem Language Result Execution time Memory
954394 2024-03-27T18:38:14 Z n1k Prisoner Challenge (IOI22_prison) C++17
72 / 100
 10 ms 1116 KB 
#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

std::vector<std::vector<int>> devise_strategy(int N) {
	int states = 24-1;

	vector v(states+1, vector<int>(N+1));

	auto get_trit = [&](auto num, auto stelle){
		for(int k=0; k<7-stelle; k++){
			num /= 3;
		}
		return num % 3;
	};


	for(int x=0; x<=states; x++){
		int stelle = (x-1)%8;
		int o_trit = (x-1)/8;
		int is_b = stelle%2;

		if(x==0)
			v[x][0] = 1;
		else
			v[x][0] = is_b;

		for(int j=0; j<N; j++){
			if(x==0){
				v[x][j+1] = 1 + 8 * get_trit(j, 0);
			}else{
				if(get_trit(j, stelle) == o_trit){
					int ntrit = get_trit(j, stelle+1);
					if(stelle==6 and (ntrit == 0 or ntrit == 2)){
						v[x][j+1] = is_b^(ntrit==0) ? -1 : -2;
					}else{
						v[x][j+1] = 8 * ntrit + stelle + 2;
					}
				}else{
					v[x][j+1] = is_b^(get_trit(j, stelle)<o_trit) ? -1 : -2;
				}
			}
		}
	}

	for(int i=0; i<=states; i++){
		for(int j=0; j<N; j++){
			v[i][j] = min(v[i][j], states);
		}
	}

	// redundant (stelle 7, trit 1)
	// redundant (stelle 7, trit 2)

	/*
	for(int i=0; i<v.size(); i++){
		for(int j=0; j<v[i].size(); j++)
			cout << v[i][j] << " ";
		cout << endl;
	}
	cout << 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 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
62.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Partially correct 1 ms 344 KB Output is partially correct
3 Partially correct 0 ms 348 KB Output is partially correct
4 Partially correct 5 ms 600 KB Output is partially correct
5 Partially correct 9 ms 1116 KB Output is partially correct
6 Partially correct 10 ms 1116 KB Output is partially correct
7 Partially correct 10 ms 1116 KB Output is partially correct
8 Partially correct 0 ms 348 KB Output is partially correct
9 Partially correct 1 ms 348 KB Output is partially correct
10 Partially correct 2 ms 348 KB Output is partially correct
11 Partially correct 5 ms 600 KB Output is partially correct
12 Partially correct 8 ms 1112 KB Output is partially correct