oj.uz

Submission #249968

# Submission time Handle Problem Language Result Execution time Memory
249968 2020-07-16T15:55:27 Z crackersamdjam Vision Program (IOI19_vision) C++14
0 / 100
 10 ms 1280 KB 
#ifndef CLION
#ifndef ONLINE_JUDGE
#define ONLINE_JUDGE
#endif
#endif

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

#ifndef ONLINE_JUDGE
template<typename T>
void print(T a){std::cout<<a<<std::endl;}
template<typename T,typename... Args>
void print(T a, Args... args) {std::cout<<a<<' ',print(args...);}
#else
#include "vision.h"
template<typename... Args>
void print(Args... args){}
#endif

#ifndef ONLINE_JUDGE
int LIM =  10000;
vector<int> all;
int eval(int i){
	return all[i];
}
int add_and(std::vector<int> Ns){
	assert(Ns.size());
	int ret = 1;
	for(int i: Ns)
		ret &= all[i];
	if(Ns.empty())
		ret = 0;
	all.emplace_back(ret);
	return all.size()-1;
}
int add_or(std::vector<int> Ns){
	assert(Ns.size());
	int ret = 0;
	for(int i: Ns)
		ret |= all[i];
	all.emplace_back(ret);
	return all.size()-1;
}
int add_xor(std::vector<int> Ns){
	assert(Ns.size());
	int ret = 0;
	for(int i: Ns)
		ret ^= all[i];
	all.emplace_back(ret);
	return all.size()-1;
}
int add_not(int N){
	all.emplace_back(!all[N]);
	return all.size()-1;
}
#else
int eval(int i){
	return 0;
}
#endif

int n, m, mx, zero;
int prea[500], pre2a[500], sufa[500], suf2a[500];
int *pre = prea+1, *pre2 = pre2a+1, *suf = sufa+1, *suf2 = suf2a+1;

bool ok(int i, int j){ return i >= 0 and i < n and j >= 0 and j < m; }
int at(int i, int j){ return i*m+j; }

int go(int k){
	//if dist >= k
	vector<int> ret = {zero};
	print("**********");
	print("try", k);
	
	for(int i = -1; i <= mx; i++){
		if(!suf[i+k])
			break;
		ret.push_back(add_and({pre[i], suf[i+k]}));
		//both are 1 means that points are >= k apart
		print("or", i, i+k, eval(ret.back()));
	}
	
	for(int i = -1; i <= mx; i++){
		if(!suf2[i+k])
			break;
		ret.push_back(add_and({pre2[i], suf2[i+k]}));
		print("or2", i, i+k, eval(ret.back()));
	}
	
	//returns if outside
	return add_or(ret);
}

void construct_network(int _n, int _m, int k){
	n = _n, m = _m;
	zero = add_and({0, 1, 2}); //must be 0
	
	mx = max(n, m);
	
	pre[-1] = zero;
	suf[mx+1] = zero;
	
	for(int i = 0; i <= mx; i++){
		vector<int> v = {pre[i-1]};
		print("in", i);
		for(int j = 0; j <= n+m; j++){
			if(ok(j, i-j)){
				print(j, i-j, "-", eval(at(j, i-j)));
				v.push_back(at(j, i-j));
			}
		}
		pre[i] = add_or(v);
		print("pre ", pre[i]);
	}
	
	for(int i = mx; i >= 0; i--){
		vector<int> v = {suf[i+1]};
		print("in", i);
		for(int j = 0; j <= n+m; j++){
			if(ok(j, i-j)){
				print(j, i-j, "-", eval(at(j, i-j)));
				v.push_back(at(j, i-j));
			}
		}
		suf[i] = add_or(v);
		print("suf ", suf[i]);
	}
	
	pre2[-1] = zero;
	suf2[mx+1] = zero;
	
	for(int i = 0; i <= mx; i++){
		vector<int> v = {pre2[i-1]};
		print("in2", i);
		for(int j = 0; j <= n+m; j++){
			if(ok(j, m-1-i+j)){
				print(j, m-1-i+j, "-", eval(at(j, m-1-i+j)));
				v.push_back(at(j, m-1-i+j));
			}
		}
		pre2[i] = add_or(v);
		print("pre ", pre2[i]);
	}
	for(int i = mx; i >= 0; i--){
		vector<int> v = {suf2[i+1]};
		print("in2", i);
		for(int j = 0; j <= n+m; j++){
			if(ok(j, m-1-i+j)){
				print(j, m-1-i+j, "-", eval(at(j, m-1-i+j)));
				v.push_back(at(j, m-1-i+j));
			}
		}
		suf2[i] = add_or(v);
		print("suf ", suf2[i]);
	}
	
	int hi = go(k+1); // if k+1 (does not) work
	int lo = go(k); // if k works
	
	int ret = add_and({add_not(hi), lo});
	print("ans", eval(hi), eval(lo), eval(ret));
}

#ifndef ONLINE_JUDGE
int main(){
	all = {0, 1, 0, 1, 0, 0};
	construct_network(2, 3, 3);
	cout<<all.back()<<endl;
}
/*
0 0 0 2
0 0 1 2
 */

//mt19937 g;
//int randint(int l, int r){ return uniform_int_distribution<int>(l, r)(g); }
//int main(int argc, char *args[]){
////	freopen("../in", "w", stdout);
//	int sd = argc > 1 ? atoi(args[1]) : 0;
//
//	sd = 10;
//
//	g = mt19937(sd);
//	int N = randint(1, 3), M = randint(1, 3);
//	if(N+M == 2)
//		M++;
//	int K = randint(1, N+M-2);
//
//	all.resize(N*M);
//
//	int AX = randint(0, N-1), AY = randint(0, M-1);
//	int BX, BY;
//	do{
//		BX = randint(0, N-1), BY = randint(0, M-1);
//	} while(BX == AX and BY == AY);
//
//	all[AX*M+AY] = all[BX*M+BY] = 1;
//
//	cout<<N<<' '<<M<<' '<<K<<endl;
//	cout<<AX<<' '<<AY<<endl;
//	cout<<BX<<' '<<BY<<endl;
//	cout<<"Reeeeee "<<AX*M+AY<<' '<<BX*M+BY<<endl;
//
//	int DIST = abs(AX-BX) + abs(AY-BY);
//	int ANS = DIST==K;
//	construct_network(N, M, K);
//	cout<<all.back()<<' '<<ANS<<endl;
//	assert(all.back() == ANS);
//}
#endif

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Incorrect 0 ms 256 KB on inputs (0, 1), (2, 0), expected 0, but computed 1
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Incorrect 0 ms 256 KB on inputs (0, 1), (2, 0), expected 0, but computed 1
14 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Incorrect 0 ms 256 KB on inputs (0, 1), (2, 0), expected 0, but computed 1
14 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Incorrect 0 ms 256 KB on inputs (0, 1), (2, 0), expected 0, but computed 1
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Incorrect 0 ms 256 KB WA in grader: Invalid index
22 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Incorrect 2 ms 384 KB on inputs (0, 0), (100, 28), expected 1, but computed 0
8 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 1280 KB on inputs (59, 80), (127, 11), expected 0, but computed 1
2 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Incorrect 0 ms 256 KB on inputs (0, 1), (2, 0), expected 0, but computed 1
14 Halted 0 ms 0 KB -