Submission #643844

#	Time	Username	Problem	Language	Result	Execution time	Memory
643844		ymm	Vision Program (IOI19_vision)	C++17	100 / 100	11 ms	1508 KiB

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;
const int BITS = 9;

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 bits = BITS)
{
	int c[BITS];
	ha(a[0], b[0], x[0], c[0]);
	Loop (i,1,bits)
		fa(a[i], b[i], c[i-1], x[i], c[i]);
}
void byte_write(int val, int x[])
{
	Loop (i,0,BITS) {
		add_xor({n+(val&1)});
		x[i] = nxt++;
		val >>= 1;
	}
}
void byte_cmp(int a[], int b[], int &x)
{
	Loop (i,0,BITS)
		add_xor({a[i], b[i]});
	vector<int> vec;
	Loop (i,0,BITS)
		vec.push_back(nxt+i);
	add_or(vec);
	add_not(nxt+BITS);
	x = nxt+BITS+1;
	nxt += BITS+2;
}

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[BITS], B[BITS];
	int dis[BITS], goal[BITS];
	Loop (dir,0,2) {
		int kooft = nxt;
		int lst = n;
		Loop (j,0,dir?h:w) {
			vector<int> vec;
			vec.push_back(lst);
			Loop (i,0,dir?w:h)
				vec.push_back(get_n(dir?j:i, dir?i:j));
			add_xor(vec);
			lst=nxt++;
		}
		int nums[1<<BITS][BITS], len=dir?h:w;
		Loop (j,0,len) {
			Loop (k,0,BITS)
				nums[j][k] = n;
			nums[j][0] = kooft+j;
		}
		for (int i = 0; len > 1; ++i) {
			for (int j = 0; j < len; j += 2) {
				if (j+1 < len)
					byte_add(nums[j], nums[j+1], nums[j/2], i+2);
				else
					memcpy(nums[j/2], nums[j], sizeof(nums[j]));
			}
			len = (len+1)/2;
		}
		memcpy(dir?B:A, nums[0], sizeof(nums[0]));
	}
	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 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 15 / 15
• Subtask 5: 12 / 12
• Subtask 6: 8 / 8
• Subtask 7: 14 / 14
• Subtask 8: 19 / 19