oj.uz

Submission #758748

# Submission time Handle Problem Language Result Execution time Memory
758748 2023-06-15T08:41:33 Z amunduzbaev Prisoner Challenge (IOI22_prison) C++17
100 / 100
 8 ms 1008 KB 
#include "prison.h"
 
#include "bits/stdc++.h"
using namespace std;
 
#ifndef EVAL
#include "grader.cpp"
#endif
 
#define ar array
typedef long long ll;
typedef int32_t ii;
//~ #define int ll
 
vector<vector<ii>> devise_strategy(ii n) {
	vector<vector<ii>> a(1, vector<ii>(n + 1));
	vector<vector<ar<int, 4>>> rng(100);
	
	a[0][0] = 1;
	int l = 1, r = n;
	a[0][l] = -2, a[0][r] = -1;
	l++, r--;
	int third = (r - l + 3) / 3;
	rng[a.size()].push_back({l - 1, r + 1, l, l + third - 1});
	for(int i=l;i<l+third;i++){
		a[0][i] = a.size();
	}
	rng[a.size() + 1].push_back({l - 1, r + 1, l + third, l + 2 * third - 1});
	for(int i=l+third;i<l+2*third;i++){
		a[0][i] = a.size() + 1;
	}
	rng[a.size() + 2].push_back({l - 1, r + 1, l + 2 * third, r});
	for(int i=l+2*third;i<=r;i++){
		a[0][i] = a.size() + 2;
	}
	vector<int> b_(n + 1, 0);
	a.push_back(b_);
	a.push_back(b_);
	a.push_back(b_);
	
	for(int b=6;b>0;b--){
		for(int j=(int)a.size() - 3;j<(int)a.size();j++){
			a[j][0] = b & 1;
			for(auto [l, r, l_, r_] : rng[j]){
				for(int k=l;k<=l_;k++){
					if(a[j][0]){
						a[j][k] = -2;
					} else {
						a[j][k] = -1;
					}
				}
				for(int k=r_;k<=r;k++){
					if(a[j][0]){
						a[j][k] = -1;
					} else {
						a[j][k] = -2;
					}
				}
				
				l_++, r_--;
				int third = (r_ - l_ + 3) / 3;
				if(b == 1) third = 2;
				{
					int _l = l_, _r = min(r_, l_ + third - 1);
					if(_l <= _r){
						rng[a.size()].push_back({l_ - 1, r_ + 1, _l, _r});
						for(int k=_l;k<=_r;k++){
							a[j][k] = a.size();
						}
					}
				}
				{
					int _l = l_ + third, _r = min(r_, l_ + 2 * third - 1);
					if(_l <= _r){
						rng[a.size() + 1].push_back({l_ - 1, r_ + 1, _l, _r});
						for(int k=_l;k<=_r;k++){
							a[j][k] = a.size() + 1;
						}
					}
				}
				{
					int _l = l_ + 2 * third, _r = r_;
					if(_l <= _r){
						rng[a.size() + 2].push_back({l_ - 1, r_ + 1, _l, _r});
						for(int k=_l;k<=_r;k++){
							a[j][k] = a.size() + 2;
						}
					}
				}
			}
			
		}
		
		a.push_back(b_);
		a.push_back(b_);
		if(b > 1) a.push_back(b_);
	}
	
	for(int j=(int)a.size() - 2;j<(int)a.size();j++){
		a[j][0] = 0;
		for(auto [l, r, l_, r_] : rng[j]){
			for(int k=l;k<=l_;k++){
				a[j][k] = -1;
			}
			for(int k=r_;k<=r;k++){
				a[j][k] = -2;
			}
			
			//~ l_++, r_--;
			//~ assert(l_ > r_);
		}
	}
	
	return a;
}

Subtask #1
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 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 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 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 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
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 276 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 7 ms 852 KB Output is correct
6 Correct 8 ms 980 KB Output is correct
7 Correct 8 ms 1008 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 4 ms 596 KB Output is correct
12 Correct 7 ms 852 KB Output is correct