Submission #428901

#	Time	Username	Problem	Language	Result	Execution time	Memory
428901		Popax21	Painting Squares (IOI20_squares)	C++14	0 / 100	1 ms	584 KiB

squares

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

struct edge;

struct node {
	std::vector<edge> edges;
	int num_in;
} nodes[512];

struct edge {
	node *nd;
	int digit;

	edge(node *n, int d) : nd(n), digit(d) {}
};

int lut[1024];

std::vector<int> paint(int n) {
	std::vector<int> l(n+1);
	l[n] = 10;

	//Create a De Brujn sequence, and store the words in a look up table
	for(int w = 0; w < 512; w++) {
		nodes[w].edges.push_back(edge(nodes + ((w<<1) | 0), 0));
		nodes[w].edges.push_back(edge(nodes + ((w<<1) | 1), 1));
		nodes[w].num_in = 2;
	}

	node *nd = &nodes[0];
	for(int i = 0; i < n; i++) {
		//Choose an edge
		std::vector<edge>::iterator ei;
		if(nd->edges.size() == 0) break;
		else if(nd->edges.size() == 1) ei = nd->edges.begin();
		else {
			if(nd->edges[0].nd->num_in == 1) ei = nd->edges.begin() + 1;
			else ei = nd->edges.begin() + 0;
		}
		edge e = *ei;

		//Delete the edge
		nd->edges.erase(ei);
		e.nd->num_in--;

		//Advance along the edge
		nd = e.nd;

		//Update the LUT
		int w = e.digit | ((nd - nodes) << 1);
		lut[w] = i;
		// printf("%d => %d [%d, %d]\n", w, i, e.digit, nd - nodes);

		l[i] = e.digit;
	}

	return l;
}

int find_location(int n, std::vector<int> c) {
	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 lut[w];
}

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