Submission #423531

#	Time	Username	Problem	Language	Result	Execution time	Memory
423531		errorgorn	Vision Program (IOI19_vision)	C++17	0 / 100	4 ms	1112 KiB

vision

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include "vision.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

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

int h,w,k;
int IDX;

int row[205]; //store entire row
int col[205]; //store entire col

int rowb[10][2]; //(is there,not there)
int colb[10][2];

int rdist[205];
int cdist[205];

void construct_network(int H, int W, int K) {
	h=H,w=W,k=K;
	IDX=h*w;
	
	rep(x,0,h){
		vector<int> v;
		rep(y,0,w) v.pub(x*w+y);
		add_or(v);
		row[x]=IDX++;
	}
	
	rep(y,0,w){
		vector<int> v;
		rep(x,0,h) v.pub(x*w+y);
		add_or(v);
		col[y]=IDX++;
	}
	
	for (int p2=1;p2<=256;p2<<=1){
		vector<int> res;
		rep(x,0,h) if (x/p2%2==0){
			vector<int> blacks;
			
			rep(y,x+1,h) if ((y-x)/p2%2==1){
				blacks.pub(row[y]);
			}
			
			if (blacks.empty()) break;
			
			add_or(blacks);
			add_and({row[x],IDX});
			res.pub(IDX+1);
			IDX+=2;
		}
		
		if (res.empty()) break;
		
		add_or(res);
		rowb[__builtin_ctz(p2)][0]=IDX;
		
		add_not(IDX);
		rowb[__builtin_ctz(p2)][1]=IDX+1;
		
		IDX+=2;
	}
	
	for (int p2=1;p2<=256;p2<<=1){
		vector<int> res;
		rep(x,0,w) if (x/p2%2==0){
			vector<int> blacks;
			
			rep(y,x+1,w) if ((y-x)/p2%2==1){
				blacks.pub(col[y]);
			}
			
			if (blacks.empty()) break;
			
			add_or(blacks);
			add_and({col[x],IDX});
			res.pub(IDX+1);
			IDX+=2;
		}
		
		if (res.empty()) break;
		
		add_or(res);
		colb[__builtin_ctz(p2)][0]=IDX;
		
		add_not(IDX);
		colb[__builtin_ctz(p2)][1]=IDX+1;
		
		IDX+=2;
	}
	
	rep(x,0,h){
		vector<int> v;
		for (int p2=1;p2<h;p2<<=1){
			if (x&p2) v.pub(rowb[__builtin_ctz(p2)][0]);
			else v.pub(rowb[__builtin_ctz(p2)][1]);
		}
		
		add_and(v);
		rdist[x]=IDX++;
	}
	
	rep(x,0,w){
		vector<int> v;
		for (int p2=1;p2<w;p2<<=1){
			if (x&p2) v.pub(colb[__builtin_ctz(p2)][0]);
			else v.pub(colb[__builtin_ctz(p2)][1]);
		}
		
		add_and(v);
		cdist[x]=IDX++;
	}
	
	vector<int> v;
	rep(x,0,h){
		int y=k-x;
		if (y<w){
			add_and({rdist[x],cdist[y]});
			v.pub(IDX);
			IDX++;
		}
	}
	
	add_or(v);
}

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