Submission #813406

#	Time	Username	Problem	Language	Result	Execution time	Memory
813406		fatemetmhr	Vision Program (IOI19_vision)	C++17	20 / 100	25 ms	5352 KiB

vision

// Comment!


#include "vision.h"
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


typedef long long ll;

#define mp     make_pair
#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 2e5 + 10;

vector <int> ns, av[2], av2[2];
int h, w, dim[2][maxn5], xdim[2][maxn5];


void construct_network(int H, int W, int k) {

	h = H;
	w = W;
	memset(dim, -1, sizeof dim);
	for(int sum = 0; sum <= h + w - 2; sum++){
		ns.clear();
		for(int i = 0; i < h; i++){
			int j = sum - i;
			if(j >= 0 && j < w)
				ns.pb(i * w + j);
		}
		sort(all(ns));
		dim[0][sum] = add_or(ns);
		xdim[0][sum] = add_xor(ns);
	}
	for(int sum = -(h - 1); sum < w; sum++){
		ns.clear();
		for(int i = 0; i < h; i++){
			int j = sum + i;
			if(j >= 0 && j < w)
				ns.pb(i * w + j);
		}
		sort(all(ns));
		dim[1][sum + h - 1] = add_or(ns);
		xdim[1][sum + h - 1] = add_xor(ns);
	}
	int eqk, eq[2], lestk, les[2];
	for(int sum = 0; sum <= h + w - 2; sum++){
		for(int tt = 0; tt < 2; tt++){
			if(sum + k <= h + w - 2){
				ns = {dim[tt][sum], dim[tt][sum + k]};
				av[tt].pb(add_and(ns));	
			}
			ns.clear();
			for(int x = 1; x <= k; x++) if(x + sum <= h + w - 2)
				ns.pb(dim[tt][x + sum]);
			int cur = -1;
			if(ns.size()){
				cur = add_or(ns);
				ns = {dim[tt][sum], cur};
				cur = add_and(ns);
			}
			int cur2 = add_not(xdim[tt][sum]);
			if(cur == -1)
				av2[tt].pb(cur2);
			else{
				ns = {cur2, dim[tt][sum]};
				cur2 = add_and(ns);
				ns = {cur, cur2};
				av2[tt].pb(add_or(ns));
			}
		}
	}
	for(int tt = 0; tt < 2; tt++){
		sort(all(av[tt]));
		eq[tt] = add_or(av[tt]);
		sort(all(av2[tt]));
		les[tt] = add_or(av2[tt]);
	}
	ns = {eq[0], eq[1]};
	eqk = add_or(ns);
	ns = {les[0], les[1]};
	lestk = add_and(ns);
	ns = {eqk, lestk};
	//cout << eq[0] + 1 << ' ' << eq[1] + 1 << ' ' << eqk + 1 << endl;
	//cout << les[0] + 1 << ' ' << les[1] + 1 << ' ' << lestk + 1 << endl;
	add_and(ns);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 15
• Subtask 5: 12 / 12
• Subtask 6: 8 / 8
• Subtask 7: 0 / 14
• Subtask 8: 0 / 19