Submission #609117

#	Time	Username	Problem	Language	Result	Execution time	Memory
609117		jophyyjh	Painting Squares (IOI20_squares)	C++14	100 / 100	377 ms	748 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
*/

#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) & (n - 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 b = 0, first = path[0]; b < k - 1; first >>= 1, b++)
        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;
}

inline vec get_seq(int n, int k) {
    vec seq;
    if (n > k) {
        seq = de_brujin(k);
        while (int(seq.size()) > n)
            seq.pop_back();
    } else {
        seq = vec(n, 1);
    }
    return seq;
}


vec paint(int n) {
    // Note that the problem requires n >= k
    vec seq = get_seq(n, std::min(n, K));
    seq.push_back(std::min(n, K));
    return seq;
}

int find_location(int n, vec c) {
    int k = c.size(), 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);
    vec seq = get_seq(n, k);
    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;
    }
    std::cerr << "error" << std::endl;
    std::abort();
}

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