Submission #430303

#	Time	Username	Problem	Language	Result	Execution time	Memory
430303		schse	Painting Squares (IOI20_squares)	C++17	0 / 100	32 ms	1600 KiB

squares

#include "squares.h"
#include <vector>
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define __K 12
std::vector<int> v;
std::set<unsigned> s;
void debuijn(unsigned int curp)
{

	for (int i = 0; i < 2; ++i)
	{
		unsigned c = curp * 2 + i;
		if (s.find(c) == s.end())
		{
			s.insert(c);
			debuijn(c % (1 << (__K)));
			v.push_back(i);
		}
	}
}

std::vector<int> paint(int n)
{
	s = {};
	v.resize(0);
	debuijn(0);
	while (v.size() > n)
		v.pop_back();
	v.push_back(__K + 1);

	return v;
}

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;
	}
	for (int i = 0; i <= n - c.size(); i++)
	{
		bool b = true;
		for (int e = 0; e < c.size(); e++)
			b &= (c[e] == v[i + e]);
		if (b)
			return i;
	}
	return -1;
}

Compilation message (stderr)

squares.cpp: In function 'std::vector<int> paint(int)':
squares.cpp:30:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |  while (v.size() > n)
      |         ~~~~~~~~~^~~
squares.cpp: In function 'int find_location(int, std::vector<int>)':
squares.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for (int i = 0; i <= n - c.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~
squares.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int e = 0; e < c.size(); e++)
      |                   ~~^~~~~~~~~~

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