Submission #444951

#	Time	Username	Problem	Language	Result	Execution time	Memory
444951		CSQ31	Vision Program (IOI19_vision)	C++17	100 / 100	99 ms	9052 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
map<int,vector<int>>lf,rg;
void construct_network(int H, int W, int k) {
	//max of
	// abs((i1+j1) - (i2+j2))
	// abs((i1-j1 - (i2+j2))
	// = k
	k++;
	map<int,vector<int>>lf,rg;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			lf[i-j].pb(i*W+j);
			rg[i+j].pb(i*W+j);
		}
	}
	int cnt = H*W-1;
	vector<int>f,g,f1,g1;
	for(auto x:lf){
		cnt++;
		add_or(x.se);
		f.pb(cnt);
		add_xor(x.se);
		add_xor({cnt,cnt+1});
		cnt+=2;
		f1.pb(cnt);
	}
	for(auto x:rg){
		cnt++;
		add_or(x.se);
		g.pb(cnt);
		add_xor(x.se);
		add_xor({cnt,cnt+1});
		cnt+=2;
		g1.pb(cnt);
	}
	vector<int>fres,gres;
	for(int i=k-1;i<sz(f);i++){
		vector<int>cur;
		for(int j=i-k+1;j<=i;j++){cur.pb(f[j]);cur.pb(f1[j]);}
		add_xor(cur);
		add_or(cur);
		add_xor({cnt+1,cnt+2});
		cnt+=3;
		fres.pb(cnt);
	}
	for(int i=k-1;i<sz(g);i++){
		vector<int>cur;
		for(int j=i-k+1;j<=i;j++){cur.pb(g[j]);cur.pb(g1[j]);}
		add_xor(cur);
		add_or(cur);
		add_xor({cnt+1,cnt+2});
		cnt+=3;
		gres.pb(cnt);
	}
	add_or(fres);
	add_or(gres);
	add_and({cnt+1,cnt+2});
	cnt+=3;
	int a = cnt;
	k--;
	fres.clear();
	gres.clear();
	for(int i=k-1;i<sz(f);i++){
		vector<int>cur;
		for(int j=i-k+1;j<=i;j++){cur.pb(f[j]);cur.pb(f1[j]);}
		add_xor(cur);
		add_or(cur);
		add_xor({cnt+1,cnt+2});
		cnt+=3;
		fres.pb(cnt);
	}
	for(int i=k-1;i<sz(g);i++){
		vector<int>cur;
		for(int j=i-k+1;j<=i;j++){cur.pb(g[j]);cur.pb(g1[j]);}
		add_xor(cur);
		add_or(cur);
		add_xor({cnt+1,cnt+2});
		cnt+=3;
		gres.pb(cnt);
	}
	add_or(fres);
	add_or(gres);
	add_and({cnt+1,cnt+2});
	cnt+=3;
	add_not(cnt);
	add_and({a,cnt+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