Submission #643814

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
643814	2022-09-23T04:42:50 Z	ymm	Vision Program (IOI19_vision)	C++17	10 / 100	17 ms	2012 KB

vision

#include "vision.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 40'010;
int h, w, k;
int n;
int nxt;

int get_n(int x, int y) { return 0 <= x && x < h && 0 <= y && y < w? x*w + y: -1;}

void ha(int a, int b, int &x, int &y)
{
	// a^b  a&b
	add_xor({a, b});
	add_and({a, b});
	x = nxt;
	y = nxt+1;
	nxt += 2;
}
void fa(int a, int b, int c, int &x, int &y)
{
	// a^b  a^b^c  a&b  (a^b)&c  (a&b)|((a^b)&c)
	add_xor({a, b});
	add_xor({nxt, c});
	add_and({a, b});
	add_and({nxt, c});
	add_or({nxt+2, nxt+3});
	x = nxt+1;
	y = nxt+4;
	nxt += 5;
}
void byte_add(int a[], int b[], int x[])
{
	int c[9];
	ha(a[0], b[0], x[0], c[0]);
	Loop (i,1,9)
		fa(a[i], b[i], c[i-1], x[i], c[i]);
}
void byte_write(int val, int x[])
{
	Loop (i,0,9) {
		add_xor({n+(val&1)});
		x[i] = nxt++;
		val >>= 1;
	}
}
void byte_cmp(int a[], int b[], int &x)
{
	Loop (i,0,9)
		add_xor({a[i], b[i]});
	add_or({nxt+0, nxt+1, nxt+2, nxt+3, nxt+4, nxt+5, nxt+6, nxt+7, nxt+8});
	add_not(nxt+9);
	x = nxt+9;
	nxt += 11;
}

void construct_network(int H, int W, int K)
{
	h = H; w = W; k = K;
	n = w*h;
	add_xor({0,0});
	add_not(n);
	nxt = n+2;
	int A[9], B[9];
	int dis[9], goal[9];
	Loop (dir,0,2) {
		int kooft = nxt;
		Loop (j,0,(dir?h:w)) {
			vector<int> vec;
			Loop (i,0,(dir?w:h))
				vec.push_back(get_n(dir?j:i, dir?i:j));
			add_xor(vec);
			nxt++;
		}
		Loop (bit,0,9) {
			int marg = nxt;
			Loop (off,0,(1<<bit)) {
				vector<int> vec;
				Loop (j,0,dir?h:w) {
					if ((j+off) & (1<<bit))
						vec.push_back(kooft+j);
				}
				vec.size()? add_xor(vec): add_xor({n});
				++nxt;
			}
			vector<int> vec;
			Loop (i,marg,nxt)
				vec.push_back(i);
			add_and(vec);
			(dir?B:A)[bit] = nxt++;
		}
	}
	byte_add(A, B, dis);
	byte_write(k, goal);
	int ans;
	byte_cmp(dis, goal, ans);
	//printf("a = %d\nb = %d\nsum = %d\nk = %d\n", n+2, n+11, dis, goal);
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Incorrect	1 ms	340 KB	on inputs (0, 0), (0, 3), expected 1, but computed 0
20	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Incorrect	1 ms	340 KB	on inputs (0, 0), (0, 3), expected 1, but computed 0
20	Halted	0 ms	0 KB	-

Subtask #4
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Incorrect	1 ms	340 KB	on inputs (0, 0), (0, 3), expected 1, but computed 0
20	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	7 ms	724 KB	on inputs (0, 0), (0, 3), expected 0, but computed 1
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	3 ms	596 KB	Output is correct
4	Incorrect	3 ms	596 KB	on inputs (0, 0), (3, 28), expected 1, but computed 0
5	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	2012 KB	Output is correct
2	Correct	1 ms	408 KB	Output is correct
3	Correct	3 ms	556 KB	Output is correct
4	Correct	5 ms	724 KB	Output is correct
5	Incorrect	5 ms	724 KB	on inputs (0, 0), (0, 3), expected 0, but computed 1
6	Halted	0 ms	0 KB	-

Subtask #8
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Incorrect	1 ms	340 KB	on inputs (0, 0), (0, 3), expected 1, but computed 0
20	Halted	0 ms	0 KB	-

Submission #643814

Compilation message