oj.uz

Submission #292979

# Submission time Handle Problem Language Result Execution time Memory
292979 2020-09-07T15:18:31 Z miss_robot Vision Program (IOI19_vision) C++14
66 / 100
 30 ms 2808 KB 
#include <bits/stdc++.h>
#include "vision.h"

#pragma GCC optimize("O3")

using namespace std;

int ab(int a, int b, int W){
	int x = a/W, X = b/W, y = a%W, Y = b%W;
	if(x > X) swap(x, X);
	if(y > Y) swap(y, Y);
	return X-x+Y-y;
}

void st1(int H, int W, int K){
	vector<int> dx(min(K,H-1)+1), dy(min(K,W-1)+1);
	vector<int> xr;
	for(int i = 0; i < H; i++){
		vector<int> x;
		for(int j = 0; j < W; j++) x.push_back(i*W+j);
		xr.push_back(add_xor(x));
		xr.back() = add_not(xr.back());
	}
	dx[0] = add_and(xr);
	xr.clear();
	for(int j = 0; j < W; j++){
		vector<int> x;
		for(int i = 0; i < H; i++) x.push_back(i*W+j);
		xr.push_back(add_xor(x));
		xr.back() = add_not(xr.back());
	}
	dy[0] = add_and(xr);
	for(int x = 1; x <= min(K,H-1); x++){
		vector<int> ask_f;
		for(int i = 0; i < H-x; i++){
			vector<int> ask;
			for(int j = 0; j < W; j++) ask.push_back(i*W+j);
			int t1 = add_or(ask);
			ask.clear();
			for(int j = 0; j < W; j++) ask.push_back((i+x)*W+j);
			int t2 = add_or(ask);
			ask_f.push_back(add_and({t1, t2}));
		}
		dx[x] = add_or(ask_f);
	}
	for(int x = 1; x <= min(K,W-1); x++){
		vector<int> ask_f;
		for(int j = 0; j < W-x; j++){
			vector<int> ask;
			for(int i = 0; i < H; i++) ask.push_back(i*W+j);
			int t1 = add_or(ask);
			ask.clear();
			for(int i = 0; i < H; i++) ask.push_back(i*W+j+x);
			int t2 = add_or(ask);
			ask_f.push_back(add_and({t1, t2}));
		}
		dy[x] = add_or(ask_f);
	}
	vector<int> fin;
	for(int i = 0; i <= min(K,H-1); i++){
		if(K-i > W-1) continue;
		fin.push_back(add_and({dx[i], dy[K-i]}));
	}
	add_or(fin);
}

void st5(int H, int W, int K){
	int c = 0;
	for(int a = 0; a < H*W; a++)
		for(int b = a+1; b < H*W; b++)
			if(ab(a, b, W) == K) add_and({a, b}), c++;
	vector<int> x;
	for(int i = H*W; i < H*W+c; i++) x.push_back(i);
	add_or(x);
}

void st6(int H, int W, int K){
	int c = 0;
	for(int i = 1; i < H*W; i++)
		if(ab(0, i, W) == K) add_and({i}), c++;
	vector<int> x;
	for(int i = H*W; i < H*W+c; i++) x.push_back(i);
	add_or(x);
}

void st7(int H, int W){
	int t1, t2;
	vector<int> f_ask;
	for(int i = 0; i < H-1; i++){
		vector<int> x, y;
		for(int j = 0; j < W; j++)
			x.push_back(i*W+j),
				y.push_back((i+1)*W+j);
		int ind1 = add_or(x), ind2 = add_or(y);
		f_ask.push_back(add_and({ind1, ind2}));
	}
	int tmp1 = add_or(f_ask), tmp2;
	f_ask.clear();
	for(int j = 0; j < W; j++){
		vector<int> x;
		for(int i = 0; i < H; i++) x.push_back(i*W+j);
		f_ask.push_back(add_xor(x));
	}
	tmp2 = add_or(f_ask);
	tmp2 = add_not(tmp2);
	t1 = add_and({tmp1, tmp2});
	f_ask.clear();
	for(int j = 0; j < W-1; j++){
		vector<int> x, y;
		for(int i = 0; i < H; i++)
			x.push_back(i*W+j),
				y.push_back(i*W+j+1);
		int ind1 = add_or(x), ind2 = add_or(y);
		f_ask.push_back(add_and({ind1, ind2}));
	}
	tmp1 = add_or(f_ask);
	f_ask.clear();
	for(int i = 0; i < H; i++){
		vector<int> x;
		for(int j = 0; j < W; j++) x.push_back(i*W+j);
		f_ask.push_back(add_xor(x));
	}
	tmp2 = add_or(f_ask);
	tmp2 = add_not(tmp2);
	t2 = add_and({tmp1, tmp2});
	add_or({t1, t2});
}

void construct_network(int H, int W, int K) {
	if(H == 1 || W == 1) st5(H, W, K);
	else if(K == 1) st7(H, W);
	else if(H <= 30 && W <= 30) st1(H, W, K);
	else st6(H, W, K);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 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 256 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 Correct 1 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 256 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 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 256 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 Correct 1 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Correct 1 ms 256 KB Output is correct
21 Correct 0 ms 256 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 360 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 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 256 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 Correct 1 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Correct 1 ms 256 KB Output is correct
21 Correct 0 ms 256 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 360 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 7 ms 768 KB Output is correct
29 Correct 0 ms 256 KB Output is correct
30 Correct 0 ms 256 KB Output is correct
31 Correct 4 ms 512 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 6 ms 768 KB Output is correct
35 Correct 9 ms 896 KB Output is correct
36 Correct 13 ms 896 KB Output is correct
37 Correct 8 ms 896 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 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 256 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 Correct 1 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Correct 1 ms 256 KB Output is correct
21 Correct 0 ms 256 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 360 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 7 ms 768 KB Output is correct
29 Correct 0 ms 256 KB Output is correct
30 Correct 0 ms 256 KB Output is correct
31 Correct 4 ms 512 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 6 ms 768 KB Output is correct
35 Correct 9 ms 896 KB Output is correct
36 Correct 13 ms 896 KB Output is correct
37 Correct 8 ms 896 KB Output is correct
38 Incorrect 0 ms 256 KB on inputs (8, 61), (22, 97), expected 1, but computed 0
39 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 1 ms 256 KB Output is correct
20 Correct 1 ms 256 KB Output is correct
21 Correct 0 ms 256 KB Output is correct
22 Correct 0 ms 256 KB Output is correct

Subtask #6
8.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 3 ms 512 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 1 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 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 372 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 256 KB Output is correct
20 Correct 16 ms 1536 KB Output is correct
21 Correct 1 ms 256 KB Output is correct
22 Correct 1 ms 256 KB Output is correct
23 Correct 1 ms 256 KB Output is correct
24 Correct 16 ms 1664 KB Output is correct
25 Correct 1 ms 256 KB Output is correct
26 Correct 1 ms 256 KB Output is correct
27 Correct 30 ms 2808 KB Output is correct
28 Correct 1 ms 256 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 256 KB Output is correct
31 Correct 1 ms 256 KB Output is correct
32 Correct 0 ms 256 KB Output is correct
33 Correct 0 ms 256 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2680 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 15 ms 1536 KB Output is correct
8 Correct 16 ms 1536 KB Output is correct
9 Correct 30 ms 2680 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 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 256 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 Correct 1 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Correct 1 ms 256 KB Output is correct
21 Correct 0 ms 256 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 360 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 7 ms 768 KB Output is correct
29 Correct 0 ms 256 KB Output is correct
30 Correct 0 ms 256 KB Output is correct
31 Correct 4 ms 512 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 6 ms 768 KB Output is correct
35 Correct 9 ms 896 KB Output is correct
36 Correct 13 ms 896 KB Output is correct
37 Correct 8 ms 896 KB Output is correct
38 Incorrect 0 ms 256 KB on inputs (8, 61), (22, 97), expected 1, but computed 0
39 Halted 0 ms 0 KB -