Submission #1311473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311473		ByeWorld	Vision Program (IOI19_vision)	C++20	100 / 100	52 ms	10500 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "Ofast")
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 5e5+100;
const int MAXA = 2e5+10;
const int SQRT = 450;
const ll INF = 2e9;
const int MOD = 998244353;
const int LOG = 60;
ll sum(auto a, auto b){ 
	ll te = a+MOD+b; 
	for(; te >= MOD; ) te -= MOD;
	return te;
}
void chsum(int &a, auto b){ a = sum(a,b); }
ll mul(auto a, auto b){ return 1ll*a*b%MOD; }
void chmul(auto &a, auto b){ a = mul(a,b); }
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }

int h, w, k;
int le[MAXN], ri[MAXN], nl[MAXN], nr[MAXN];
int dl[MAXN], dr[MAXN];
pii L[MAXN], R[MAXN];

int gan(int x, int y){
	return (x-1)*w+y-1;
}

int cek(int jar){
	// ri or diag
	int num = 0;
	for(int i=h; i>=2; i--){
		vector<int> vec;
		int r=i, c=1;
		while(r<=h && c<=w){
			vec.pb(gan(r,c)); r++; c++;
		}
		ri[++num] = add_or(vec);
		R[num] = {i, 1};
	}
	for(int i=1; i<=w; i++){
		vector<int> vec;
		int r=1, c=i;
		while(r<=h && c<=w){
			vec.pb(gan(r,c)); r++; c++;
		}
		ri[++num] = add_or(vec);
		R[num] = {1, i};
	}
	// le or diag
	num = 0;
	for(int i=h; i>=2; i--){
		vector<int> vec;
		int r=i, c=w;
		while(r<=h && c>=1){
			vec.pb(gan(r,c)); r++; c--;
		}
		le[++num] = add_or(vec);
		L[num] = {i, w};
	}
	for(int i=w; i>=1; i--){
		vector<int> vec;
		int r=1, c=i;
		while(r<=h && c>=1){
			vec.pb(gan(r,c)); r++; c--;
		}
		le[++num] = add_or(vec);
		L[num] = {1, i};
	}

	int siz = h+w-1;
	num=0;
	for(int i=1; i<=siz; i++){
		vector<int> vec;
		for(int p=max(1, i-jar); p<=min(siz, i+jar); p++){
			if(p==i) continue;
			vec.pb(le[p]);
		}
		int OR = add_or(vec);
		nl[++num] = add_and({le[i], OR});
	}
	
	num=0;
	for(int i=1; i<=siz; i++){
		vector<int> vec;
		for(int p=max(1, i-jar); p<=min(siz, i+jar); p++){
			if(p==i) continue;
			vec.pb(ri[p]);
		}
		int OR = add_or(vec);
		nr[++num] = add_and({ri[i], OR});
	}

	//apakah double?
	num=0;
	for(int i=1; i<=siz; i++){
		vector<int> vec;
		int r=L[i].fi, c=L[i].se;
		while(r<=h && c>=1){
			vec.pb(gan(r,c));
			r++; c--;
		}
		int OR = le[i];
		int XOR = add_xor(vec);
		int N = add_not(XOR);
		dl[++num] = add_and({OR, N});
	}
	num=0;
	for(int i=1; i<=siz; i++){
		vector<int> vec;
		int r=R[i].fi, c=R[i].se;
		while(r<=h && c<=w){
			vec.pb(gan(r,c));
			r++; c++;
		}
		// int OR = add_or(vec);
		int OR = ri[i];
		int XOR = add_xor(vec);
		int N = add_not(XOR);
		dr[++num] = add_and({OR, N});
	}

	int up, dw;
	{
		vector<int> vec;
		for(int i=1; i<=siz; i++){
			vec.pb(nl[i]); vec.pb(dl[i]);
		}
		up = add_or(vec);
	}
	{
		vector<int> vec;
		for(int i=1; i<=siz; i++){
			vec.pb(nr[i]); vec.pb(dr[i]);
		}
		dw = add_or(vec);
	}
	return add_and({up, dw});
}
void construct_network(int H, int W, int K) {
	h = H; w = W; k = K;
	if(k==1){
		int nw = cek(k);
	} else {
		int bef = cek(k-1);
		int nw = cek(k);
		int x = add_xor({bef, nw});
	}
}

• 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