제출 #429239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429239		Popax21	Painting Squares (IOI20_squares)	C++14	100 / 100	162 ms	556 KiB

squares

#include <stddef.h>
#include <stdio.h>
#include <assert.h>
#include <vector>
#include "squares.h"

struct edge;

int seq[2048], iseq[1024], seqi = 0;
void deBrujinSeq(int w) {
	static bool v[512][2] = {0};
	for(int i = 0; i < 2; i++) {
		if(!v[w][i]) {
			v[w][i] = true;
			deBrujinSeq(((w << 1) | i) & 511);
			seq[seqi++] = i;
		}
	}
}

void init() {
	static bool initalized = false;
	if(initalized) return;
	initalized = true;

	//Create a De Brujn sequence
	deBrujinSeq(0);

	//Create a reverse lookup table
	std::fill(iseq+0, iseq+1024, -1);
	for(int i = 0; i <= 1024-10; i++) {
		int w = 0;
		for(int j = 0; j < 10; j++) {
			assert(seq[i+j] >= 0);
			w = (w << 1) | seq[i+j];
		}
		assert(iseq[w & 1023] < 0);
		iseq[w & 1023] = i;
	}
}

std::vector<int> paint(int n) {
	init();
	
	//Init labels from sequence
	std::vector<int> l(n+1);
	for(int i = 0; i < n; i++) l[i] = seq[i];
	l[n] = 10;

	return l;
}

int find_location(int n, std::vector<int> c) {
	init();
	assert(c.size() == 10);

	//Is at edge?
	if(c[9] < 0) {
		int p = 0;
		while(c[p] >= 0) p++;
		return n - p;
	}

	//Calculate word
	int w = 0;
	for(int i = 0; i < 10; i++) {
		assert(c[i] >= 0);
		w = (w << 1) | c[i];
	}

	//Lookup in LUT
	return iseq[w & 1023];
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55