Submission #307248

#	Time	Username	Problem	Language	Result	Execution time	Memory
307248		tincamatei	Painting Squares (IOI20_squares)	C++14	100 / 100	139 ms	996 KiB

squares

#include "squares.h"
#include <vector>
#include <algorithm>
#include <cstdio>

struct Edge {
    int b, c;
    bool marked;
};

std::vector<Edge> debrujin[1<<9];
std::vector<int> magic;

void euler(int nod) {
    int i = 0;
    while(i < debrujin[nod].size()) {
        while(i < debrujin[nod].size() && debrujin[nod][i].marked)
            ++i;
        if(i < debrujin[nod].size()) {
            debrujin[nod][i].marked = true;
            euler(debrujin[nod][i].b);
            magic.push_back(debrujin[nod][i].c);
        }
    }
}

std::vector<int> paint(int n) {
	std::vector<int> labels(n + 1, 1);
	int k = 10;

    for(int i = 0; i < (1 << (k - 1)); ++i) {
        debrujin[i].push_back({(i << 1) & ((1 << (k - 1)) - 1), 0, false});
        debrujin[i].push_back({((i << 1) | 1) & ((1 << (k - 1)) - 1), 1, false});
    }

    euler(0);

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

    std::reverse(magic.begin(), magic.end());

    for(int i = 0; i < n; ++i)
        labels[i] = magic[i];

    labels[n] = k;
    return labels;
}

bool built = false;
int table[1<<10];

int find_location(int n, std::vector<int> c) {
    int k = 10;
    if(!built) {
        built = true;
        std::vector<int> labels = paint(n);
        for(int i = 0; i + k - 1 < magic.size(); ++i) {
            int val = 0;
            for(int j = 0; j < k; ++j)
                val = val * 2 + magic[i + j];
        
            table[val] = i;
        }
    }

    int i = 0, val = 0;
    while(i < k && c[i] != -1) {
        val = val * 2 + c[i];
        ++i;
    }

    if(i < k)
        return n - i;

    return table[val];
}

Compilation message (stderr)

squares.cpp: In function 'void euler(int)':
squares.cpp:16:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     while(i < debrujin[nod].size()) {
      |           ~~^~~~~~~~~~~~~~~~~~~~~~
squares.cpp:17:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         while(i < debrujin[nod].size() && debrujin[nod][i].marked)
      |               ~~^~~~~~~~~~~~~~~~~~~~~~
squares.cpp:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         if(i < debrujin[nod].size()) {
      |            ~~^~~~~~~~~~~~~~~~~~~~~~
squares.cpp: In function 'int find_location(int, std::vector<int>)':
squares.cpp:58:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(int i = 0; i + k - 1 < magic.size(); ++i) {
      |                        ~~~~~~~~~~^~~~~~~~~~~~~~

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