Submission #355372

#	Time	Username	Problem	Language	Result	Execution time	Memory
355372		dolphingarlic	Painting Squares (IOI20_squares)	C++14	100 / 100	394 ms	732 KiB

squares

#include "squares.h"

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

bool visited[1024];
int k, ord[1024], N;
vector<int> de_bruijn;

void dfs(int node) {
    for (int i : {0, 1}) {
        int nxt = node + (i << k - 1);
        if (!visited[nxt]) {
            visited[nxt] = 1;
            dfs(nxt >> 1);
            de_bruijn.push_back(i);
        }
    }
}

vector<int> paint(int n) {
    memset(visited, 0, sizeof visited);
    de_bruijn.clear();
    k = min(10, n);
    dfs(0);
    for (int i = 1; i < k; i++) de_bruijn.push_back(0);
    while (de_bruijn.size() > n) de_bruijn.pop_back();
    for (int i = 0; i <= de_bruijn.size() - k; i++) {
        int hsh = 0;
        for (int j = i; j < i + k; j++) hsh = (hsh << 1) + de_bruijn[j];
        ord[hsh] = i;
    }
    de_bruijn.push_back(k);
    return de_bruijn;
}

int find_location(int n, vector<int> c) {
    memset(visited, 0, sizeof visited);
    de_bruijn.clear();
    k = min(10, n);
    dfs(0);
    for (int i = 0; i <= de_bruijn.size() - k; i++) {
        int hsh = 0;
        for (int j = i; j < i + k; j++) hsh = (hsh << 1) + de_bruijn[j];
        ord[hsh] = i;
    }
    int hsh = 0;
    for (int i = 0; i < c.size(); i++) {
        if (c[i] == -1) return n - i;
        hsh = (hsh << 1) + c[i];
    }
    return ord[hsh];
}

Compilation message (stderr)

squares.cpp: In function 'void dfs(int)':
squares.cpp:12:34: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   12 |         int nxt = node + (i << k - 1);
      |                                ~~^~~
squares.cpp: In function 'std::vector<int> paint(int)':
squares.cpp:27:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |     while (de_bruijn.size() > n) de_bruijn.pop_back();
      |            ~~~~~~~~~~~~~~~~~^~~
squares.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i = 0; i <= de_bruijn.size() - k; i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~
squares.cpp: In function 'int find_location(int, std::vector<int>)':
squares.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 0; i <= de_bruijn.size() - k; i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~
squares.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < c.size(); i++) {
      |                     ~~^~~~~~~~~~

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