Submission #559449

#	Time	Username	Problem	Language	Result	Execution time	Memory
559449		ahmet34	Painting Squares (IOI20_squares)	C++14	100 / 100	159 ms	496 KiB

squares

#include "squares.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

const int INF = 2e9, N = 1005, M = 1e9+7, LOG = 16;
const ll LINF = 1e18;

int len;
string res;
map<string, bool> vis;

void dfs(string node) {
    for(int i = 0; i < 2; i++) {
        string to = node + char('0' + i);
        if(!vis[to]) {
            vis[to] = true;
            dfs(to.substr(1));
            res += to.back();
        }
    }
}

void deBruijn () {
	vis.clear();
	res.clear();
	string s = string(len-1, '0');
    dfs(s);
    res += s;
}

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

	/*
	len = min(10, n);
	deBruijn();

	for(int i = 0; i < n; ++i)
		labels[i] = res[i]-'0';

	labels.push_back(len);
	*/
	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, vector<int> c) {
	vector<int> labels;

	/*
	len = min(10, n);
	deBruijn();

	for(int i = 0; i < n; ++i)
		labels[i] = res[i]-'0';
	*/
	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);

	for(int i = 0; i < n; i++) {
		if(equal(all(c), labels.begin()+i, labels.begin()+i+k+1))
			return i;
	}
	return -1;
}

Compilation message (stderr)

squares.cpp: In function 'std::vector<int> paint(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: In function 'int find_location(int, std::vector<int>)':
squares.cpp:100:26: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
  100 |   graph[m][1] = (m << 1) & ((1 << k) - 1) | 1;
      |                 ~~~~~~~~~^~~~~~~~~~~~~~~~
squares.cpp:107:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |  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:123:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  123 |  assert(labels.size() == n);
      |         ~~~~~~~~~~~~~~^~~~

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