Submission #609043

#	Time	Username	Problem	Language	Result	Execution time	Memory
609043		jophyyjh	Painting Squares (IOI20_squares)	C++14	0 / 100	3 ms	760 KiB

squares

/**
 * I'm a bit disappointed. Since only k <= 10 can AC, i think the only solution would
 * be to use De Brujin Sequence. k = 10 is already the minimum since it's the
 * smallest positive int satisfying 2^k + k - 1 >= n. (I was looking for sth original
 * when I started this problem.)
 * 
 *      K:  log_2(n)        (as long as 2^k + k - 1 >= n)
 * Implementation 1         (Solves [S1-3], [S5], [S6])
*/

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

typedef std::vector<int>	vec;

const int K = 10;


std::vector<vec> graph;
vec path;

void find_path(int k) {
    while (!graph[k].empty()) {
        int j = graph[k][graph[k].size() - 1];
        graph[k].pop_back();
        find_path(j);
    }
    path.push_back(k);
}

vec de_brujin(int k) {
    path.clear();
    int n = 1 << (k - 1);
    graph.assign(n, vec());
    for (int i = 0; i < n; i++) {
        int j = (i << 1) & ((1 << (k - 1)) - 1);
        graph[i].push_back(j);
        graph[i].push_back(j | 1);
    }
    find_path(0);
    std::reverse(path.begin(), path.end());

    vec seq;
    for (int first = path[0]; first > 0; first >>= 1)
        seq.push_back(first & 1);
    std::reverse(seq.begin(), seq.end());
    for (int i = 1; i < int(path.size()); i++)
        seq.push_back(path[i] & 1);
    return seq;
}

vec seq;

vec paint(int n) {
    seq = de_brujin(K);
    while (int(seq.size()) > n)
        seq.pop_back();
    seq.push_back(K);
    return seq;
}

int find_location(int n, vec c) {
    assert(int(c.size()) == K);
    int out_of_bound = 0;
    for (int i = K - 1; i >= 0 && c[i] == -1; i--)
        out_of_bound++;
    if (out_of_bound > 0)
        return n - (K - out_of_bound);
    for (int start = 0; start + K - 1 < n; start++) {
        bool equal = true;
        for (int i = 0; i < K && equal; i++)
            equal &= (seq[start + i] == c[i]);
        if (equal)
            return start;
    }
    return -1;  // error
}

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