Submission #430422

#	Time	Username	Problem	Language	Result	Execution time	Memory
430422		schse	Painting Squares (IOI20_squares)	C++17	0 / 100	106 ms	600 KiB

squares

#include "squares.h"
#include <vector>
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;

bool seen[1024 + 10];
vector<int> edges;
int pos[1024];
vector<int> debj;

void dfs(int node)
{
	for (int i = 0; i < 2; i++)
	{
		int cn = node * 2 + i;
		if (!seen[cn])
		{
			seen[cn] = true;
			dfs(cn & 511);
			edges.push_back(i);
		}
	}
}

vector<int> deBruijn(int n)
{
	fill(seen, seen + 1024, 0);
	edges.clear();
	dfs(0);

	for (int i = 0; i < 10; i++)
		edges.push_back(0);

	vector<int> v;
	for (int i = 0; i < edges.size() - 10; i++)
	{
		int c = 0;
		for (int e = 0; e < 10; e++)
		{
			c = c * 2 + edges[i + e];
		}
		pos[c] = i;
	}
	for (int i = 0; i < n; i++)
		v.push_back(edges[i]);
	v.push_back(10);
	return v;
}

std::vector<int> paint(int n)
{
	return deBruijn(n);
}

int find_location(int n, std::vector<int> c)
{
	if (c.back() == -1)
	{
		int p = n - c.size();
		while (c.back() == -1)
		{
			p++;
			c.pop_back();
		}
		return p;
	}
	int b = 0;
	for (int i = 0; i < c.size(); i++)
	{
		b = b * 2 + c[i];
	}
	return pos[b];
}

Compilation message (stderr)

squares.cpp: In function 'std::vector<int> deBruijn(int)':
squares.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i = 0; i < edges.size() - 10; i++)
      |                  ~~^~~~~~~~~~~~~~~~~~~
squares.cpp: In function 'int find_location(int, std::vector<int>)':
squares.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i = 0; i < c.size(); i++)
      |                  ~~^~~~~~~~~~

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