Submission #733734

#	Time	Username	Problem	Language	Result	Execution time	Memory
733734		sentheta	Vision Program (IOI19_vision)	C++17	59 / 100	33 ms	4280 KiB

vision

#include "vision.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;


int h, w;
int f(int i,int j){
	return i*w+j;
}

V<int> v[2][500];
int one[2][500], two[2][500];

// check if distance is <=k
int solve(int k){
	// +/- diagonals
	int ret[2];
	rep(t,0,2){
		V<int> results;
		for(int l=0,r=k; r<h+w; l++,r++){
			bool allempty = 1;
			rep(i,l,r+1) allempty &= v[t][i].empty();
			if(allempty) continue;

			// pixels in different diags
			V<int> tmp;
			rep(i,l,r+1) if(!v[t][i].empty()){
				tmp.push_back(one[t][i]);
			}
			int a = add_or(tmp);
			int b = add_xor(tmp);
			// a and not b
			int nb = add_not(b);
			int c = add_and({a, nb});
			results.push_back(c);

			// pixels in same diags
			tmp.clear();
			rep(i,l,r+1) if(!v[t][i].empty()){
				tmp.push_back(two[t][i]);
			}
			int d = add_or(tmp);
			results.push_back(d);
		}

		ret[t] = add_or(results);
		cout << nl;
	}

	return add_and({ret[0], ret[1]});
}

void construct_network(int _h,int _w,int _k){
	h = _h; w = _w; int k = _k;

	// group by diagonals
	rep(t,0,2){
		rep(i,0,h) rep(j,0,w){
			if(t==0) v[t][i+j].push_back(f(i,j));
			else v[t][i-j+w-1].push_back(f(i,j));
		}

		rep(i,0,h+w) if(!v[t][i].empty()){
			// dbg(i);
			// for(int x : v[t][i]) cout << x << " ";
			// cout << nl;

			one[t][i] = add_or(v[t][i]);
			
			int tmp = add_xor(v[t][i]);
			tmp = add_not(tmp);

			two[t][i] = add_and({one[t][i], tmp});
		}
	}

	int a = solve(k);
	// dbg(a);
	// cout << nl << nl;
	int b = solve(k-1);
	// dbg(b);

	// a and (not b)
	int nb = add_not(b);
	int c = add_and({a, nb});
	return;

	// V<int> Ns;
	// Ns = {0, 1};
	// int a = add_and(Ns);
	// Ns = {0, a};
	// int b = add_or(Ns);
	// Ns = {0, 1, b};
	// int c = add_xor(Ns);
	// add_not(c);
}

Compilation message (stderr)

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:117:6: warning: unused variable 'c' [-Wunused-variable]
  117 |  int c = add_and({a, nb});
      |      ^

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