Submission #246790

#	Time	Username	Problem	Language	Result	Execution time	Memory
246790		Evirir	Vision Program (IOI19_vision)	C++17	100 / 100	43 ms	4156 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<x<<endl
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_by_key
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void SD(int t=0){ cout<<"TEST "<<t<<endl; }

const int MAXN = 405;
const int MOD = 1e9+7;
bool DEBUG=0;
/*
int add_and(std::vector<int> Ns);
int add_or(std::vector<int> Ns);
int add_xor(std::vector<int> Ns);
int add_not(int N);
*/

int dist(ii a, ii b)
{
	return abs(a.F-b.F)+abs(a.S-b.S);
}

vi v;
int off;

vector<int> d1[MAXN],d2[MAXN];
int t1[2],t2[2];

void construct_network(int n, int m, int K)
{
	if(n*m==2){
		add_or({0,1});
		return;
	}
	
	off=m-1;
	vi all;
	
	for(int i=0;i<n;i++) for(int j=0;j<m;j++)
	{
		all.pb(i*m+j);
		d1[i+j].pb(i*m+j);
		d2[i-j+off].pb(i*m+j);
	}
	
	//create dummy 0 and 1
	int zero = add_and(all);
	int one = add_or(all);
	
	forn(i,0,m+n-1)
	{
		int tmp=add_or(d1[i]);
		if(i==0) t1[0]=tmp;
		if(i==m+n-2) t1[1]=tmp;
	}
	forn(i,0,m+n-1)
	{
		int tmp=add_or(d2[i]);
		if(i==0) t2[0]=tmp;
		if(i==m+n-2) t2[1]=tmp;
	}
	
	vi exact,test;
	
	//----------------------------------------------
	//d1 K, d2 large
	for(int i=t1[0];i+K<=t1[1];i++)
	{
		v={i,i+K};
		exact.pb(add_and(v)); if(DEBUG) cout<<"exact: "<<exact.back()<<endl;
	}
	for(int i=t2[0];i+K+1<=t2[1];i++)
	{
		v.clear();
		for(int j=i+K+1;j<=t2[1];j++) v.pb(j);
		test.pb(add_and({i,add_or(v)})); if(DEBUG) cout<<"test: "<<test.back()<<endl;
	}
	
	int f1,f2;
	int final1, final2;
	
	if(DEBUG){
		cout<<"exact.size()="<<exact.size()<<endl;
		cout<<"test.size()="<<test.size()<<endl;
	}
	
	f1 = (exact.size() ? add_or(exact) : zero);
	f2 = (test.size() ? add_not(add_or(test)) : one);
	
	v = {f1,f2}; if(DEBUG){ watch(f1); watch(f2); }
	final1=add_and(v);
	//phase 1 end
	//----------------------------------------------
	
	exact.clear(); test.clear(); v.clear();
	
	//----------------------------------------------
	//d2 exact, d1 large
	for(int i=t2[0];i+K<=t2[1];i++)
	{
		v={i,i+K};
		exact.pb(add_and(v)); if(DEBUG) cout<<"exact: "<<exact.back()<<endl;
	}
	for(int i=t1[0];i+K+1<=t1[1];i++)
	{
		v.clear();
		for(int j=i+K+1;j<=t1[1];j++) v.pb(j);
		test.pb(add_and({i,add_or(v)})); if(DEBUG) cout<<"test: "<<test.back()<<endl;
	}
	
	f1 = (exact.size() ? add_or(exact) : zero);
	f2 = (test.size() ? add_not(add_or(test)) : one);
	
	v = {f1,f2}; if(DEBUG){ watch(f1); watch(f2); }
	final2=add_and(v);
	//phase 2 end
	//----------------------------------------------
	
	//----------------------------------------------
	//check one of them is correct
	v = {final1, final2};
	add_or(v);
}

• 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