oj.uz

Submission #782785

# Submission time Handle Problem Language Result Execution time Memory
782785 2023-07-14T09:20:15 Z Tekor Prisoner Challenge (IOI22_prison) C++17
100 / 100
 9 ms 1456 KB 
#include "prison.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define en '\n'
const int M = 30;
const int N = 5e3 + 10;
int a[M][N],k;
void build(int step,int type,int l,int r) {
	if(l > r)return;
	int pos = step * 3 - type;
	k = max(k,pos);
	a[pos][0] = step % 2;
	//cout << pos << " " << type << " " << l << " " << r << en;
	if(l == r) {
		a[pos][l] = -1;
		return;
	}
	int w1 = 0,w2 = 0;
	if(step % 2 == 0) {
		a[pos][l] = -1;
		a[pos][r] = -2;
		w1 = -1;
		w2 = -2;
	}else {
		a[pos][l] = -2;
		a[pos][r] = -1;
		w1 = -2;
		w2 = -1;
	}
	l++;
	r--;
	if(l > r)return;
	int sz = r - l + 1;
	int sz1 = sz / 3,sz2 = sz / 3,sz3 = sz / 3;
	if(sz % 3 >= 1)sz1++;
	if(sz % 3 == 2)sz2++;
	int pos1 = (step + 1) * 3 - 2,pos2 = (step + 1) * 3 - 1,pos3 = (step + 1) * 3;
	if(sz == 2) {
		sz1 = 2;
		sz2 = 0;
	}else if(sz == 3) {
		sz1 = 2;
		sz2 = 1;
		sz3 = 0;
	}else if(sz == 4) {
		sz1 = 2;
		sz2 = 2;
		sz3 = 0;
	}
	a[pos1][l - 1] = w2;
	a[pos1][r + 1] = w1;
	if(sz2 > 0) {
		a[pos2][l - 1] = w2;
		a[pos2][r + 1] = w1;
	}
	if(sz3 > 0) {
		a[pos3][l - 1] = w2;
		a[pos3][r + 1] = w1;
	}
	for(int i = l;i <= l + sz1 - 1;i++) {
		a[pos][i] = (step + 1) * 3 - 2;
		a[pos2][i] = w2;
		a[pos3][i] = w2;
	} 
	for(int i = l + sz1;i <= l + sz1 + sz2 - 1;i++) {
		a[pos][i] = (step + 1) * 3 - 1;
		a[pos1][i] = w1;
		a[pos3][i] = w2;
	}
	for(int i = l + sz1 + sz2;i <= r;i++) {
		a[pos][i] = (step + 1) * 3;
		a[pos1][i] = w1;
		a[pos2][i] = w1;
	}
	build(step + 1,2,l,l + sz1 - 1);
	if(sz2)build(step + 1,1,l + sz1,l + sz1 + sz2 - 1);
	if(sz3)build(step + 1,0,l + sz1 + sz2,r);
}

vector< vector<int> > devise_strategy(int n) {
	build(0,0,1,n);
	vector <vector <int> > ans;
	//cout << k << en;
	for(int i = 0;i <= k;i++) {
		vector <int> tek;
		for(int j = 0;j <= n;j++) {
			tek.pb(a[i][j]);
			//cout << a[i][j] << " ";
			assert(a[i][j] <= k);
		}
		//cout << en;
		ans.pb(tek);
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 432 KB Output is correct
7 Correct 0 ms 340 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 312 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 312 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 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 7 ms 1352 KB Output is correct
6 Correct 9 ms 1364 KB Output is correct
7 Correct 8 ms 1456 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 436 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 7 ms 1328 KB Output is correct