Submission #559298

#	Time	Username	Problem	Language	Result	Execution time	Memory
559298		AlperenT	Painting Squares (IOI20_squares)	C++17	100 / 100	175 ms	588 KiB

squares

#include "squares.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> paint(int n){
	vector<int> labels;

	int k = min(n - 1, 9);

	vector<array<int, 2>> graph(1 << k, {-1, -1});

	for(int m = 0; m < 1 << k; m++){
		graph[m][0] = (m << 1) & ((1 << k) - 1);
		graph[m][1] = (m << 1) & ((1 << k) - 1) | 1;
	}

	for(int i = 0; i < k; i++) labels.push_back(0);

	int v = 0, u;

	while(labels.size() < n){
		if(graph[v][1] != -1){
			u = graph[v][1];
			graph[v][1] = -1;
			labels.push_back(1);
			v = u;
		}
		else if(graph[v][0] != -1){
			u = graph[v][0];
			graph[v][0] = -1;
			labels.push_back(0);
			v = u;
		}
		else break;
	}

	assert(labels.size() == n);

	labels.push_back(k + 1);

	return labels;
}

int find_location(int n, std::vector<int> c) {
	vector<int> labels;

	int k = min(n - 1, 9);

	vector<array<int, 2>> graph(1 << k, {-1, -1});

	for(int m = 0; m < 1 << k; m++){
		graph[m][0] = (m << 1) & ((1 << k) - 1);
		graph[m][1] = (m << 1) & ((1 << k) - 1) | 1;
	}

	for(int i = 0; i < k; i++) labels.push_back(0);

	int v = 0, u;

	while(labels.size() < n){
		if(graph[v][1] != -1){
			u = graph[v][1];
			graph[v][1] = -1;
			labels.push_back(1);
			v = u;
		}
		else if(graph[v][0] != -1){
			u = graph[v][0];
			graph[v][0] = -1;
			labels.push_back(0);
			v = u;
		}
		else break;
	}

	assert(labels.size() == n);

	for(int i = 0; i < k; i++) labels.push_back(-1);

	k++;

	for(int i = 0; i < labels.size(); i++){
		if(equal(labels.begin() + i, labels.begin() + i + k, c.begin(), c.end())) return i;
	}

	return -1;
}

Compilation message (stderr)

squares.cpp: In function 'std::vector<int> paint(int)':
squares.cpp:15:26: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   15 |   graph[m][1] = (m << 1) & ((1 << k) - 1) | 1;
      |                 ~~~~~~~~~^~~~~~~~~~~~~~~~
squares.cpp:22:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |  while(labels.size() < n){
      |        ~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from squares.cpp:2:
squares.cpp:38:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |  assert(labels.size() == n);
      |         ~~~~~~~~~~~~~~^~~~
squares.cpp: In function 'int find_location(int, std::vector<int>)':
squares.cpp:54:26: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   54 |   graph[m][1] = (m << 1) & ((1 << k) - 1) | 1;
      |                 ~~~~~~~~~^~~~~~~~~~~~~~~~
squares.cpp:61:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |  while(labels.size() < n){
      |        ~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from squares.cpp:2:
squares.cpp:77:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |  assert(labels.size() == n);
      |         ~~~~~~~~~~~~~~^~~~
squares.cpp:83:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for(int i = 0; i < labels.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~

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