Submission #716388

#	Time	Username	Problem	Language	Result	Execution time	Memory
716388		myrcella	Vision Program (IOI19_vision)	C++17	100 / 100	41 ms	4528 KiB

vision

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
#include "vision.h"

vector <int> leftdiag,rightdiag;
int cnt = 0;

int check(int x) {
	add_xor(leftdiag); //1 -> same left diagnal
	vector <int> q;
	q.pb(cnt);
	cnt++;
	rep(i,0,SZ(leftdiag)) {
		if (i+x >= SZ(leftdiag)) break;
		vector <int> tmp;
		rep(j,i,i+x+1) {
			tmp.pb(leftdiag[j]);
		}
		add_or(tmp);
		add_xor(tmp);
		add_not(cnt+1);
		add_and({cnt,cnt+2});
		q.pb(cnt+3);
		cnt+=4;
	}
	add_or(q);
	int id1 = cnt++;
	
	add_xor(rightdiag); //1 -> same right diagnal
	while (!q.empty()) q.pop_back();
	q.pb(cnt);
	cnt++;
	rep(i,0,SZ(rightdiag)) {
		if (i+x >= SZ(rightdiag)) break;
		vector <int> tmp;
		rep(j,i,i+x+1) {
			tmp.pb(rightdiag[j]);
		}
		add_or(tmp);
		add_xor(tmp);
		add_not(cnt+1);
		add_and({cnt,cnt+2});
		q.pb(cnt+3);
		cnt+=4;
	}
	add_or(q);
	int id2 = cnt++;
	add_and({id1,id2});
	return cnt++;
}

void construct_network(int H, int W, int K) {
	cnt = H*W;
	for (int i=H-1;i>0;i--) {
		int x = i,y = 0;
		vector <int> tmp;
		while (x<H and y<W) {
			tmp.pb(x*W+y);
			x++,y++;
		}
		leftdiag.pb(cnt);
		add_or(tmp);
		cnt++;
	}
	for (int i=0;i<W;i++) {
		int x = 0,y = i;
		vector <int> tmp;
		while (x<H and y<W) {
			tmp.pb(x*W+y);
			x++,y++;
		}
		leftdiag.pb(cnt);
		add_or(tmp);
		cnt++;
	}
	rep(i,0,W) {
		int x = 0,y = i;
		vector <int> tmp;
		while (x<H and y>=0) {
			tmp.pb(x*W+y);
			x++,y--;
		}
		rightdiag.pb(cnt);
		add_or(tmp);
		cnt++;
	}
	rep(i,1,H) {
		int x = i,y = W-1;
		vector <int> tmp;
		while (x<H and y>=0) {
			tmp.pb(x*W+y);
			x++,y--;
		}
		rightdiag.pb(cnt);
		add_or(tmp);
		cnt++;
	}
	int id1 = check(K-1);
	int id2 = check(K);
	add_not(id1);
	add_and({id2,id2+1});
}

• 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