Submission #810961

#	Time	Username	Problem	Language	Result	Execution time	Memory
810961		Username4132	Vision Program (IOI19_vision)	C++14	100 / 100	37 ms	4156 KiB

vision

#include "vision.h"
#include<iostream>
#include<vector>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back

int tc, fc; // cuidado con 2x1

int myand(vector<int> vec){
	vec.PB(tc);
	return add_and(vec);
}

int myor(vector<int> vec){
	vec.PB(fc);
	return add_or(vec);
}

int myxor(vector<int> vec){
	vec.PB(fc);
	return add_xor(vec);
}


// chequear si no se rompe cuando n es 1
vector<int> solve(int offset, int n){
	int lg = 8*sizeof(int) - __builtin_clz(n);

	vector<int> notMul(n+1);
	forsn(i, 2, n) {
		vector<int> def;
		forn(j, lg) {
			vector<int> ask;
			forn(k, n) if((k%i)&(1<<j)) ask.PB(offset + k);
			def.PB(myxor(ask));
		}
		notMul[i]=myor(def);
	}
	vector<int> exact(n);

	vector<int> edge;
	forn(i, n) edge.PB(offset + i);
	int xx = myor(edge);
	exact[0] = add_not(xx);
	edge.clear();
	forsn(i, 2, n) edge.PB(notMul[i]);
	edge.PB(xx);
	exact[1]=myand(edge);


	forsn(i, 2, n){
		vector<int> mul;
		for(int j=2*i; j<n; j+=i) mul.PB(notMul[j]);
		int x = myand(mul);
		int y = add_not(notMul[i]);
		exact[i] = myand({x, y, xx});
	}

	return exact;
}

void construct_network(int H, int W, int K) {

	forn(i, H){
		vector<int> ask;
		forn(j, W) ask.PB(i*W + j);
		add_xor(ask);
	}

	forn(j, W){
		vector<int> ask;
		forn(i, H) ask.PB(i*W + j);
		add_xor(ask);
	}

	vector<int> al;
	forn(i, H*W) al.PB(i);
	tc = add_or(al);
	fc = add_not(tc);

	vector<int> sh = solve(H*W, H);
	vector<int> sv = solve(H*(W+1), W);

	vector<int> fin;
	forn(i, K+1) if((i<(int)sh.size()) && (K-i<(int)sv.size())){
		fin.PB(myand({sh[i], sv[K-i]}));
	}
	myor(fin);
}

• 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