Submission #372301

#	Time	Username	Problem	Language	Result	Execution time	Memory
372301		Lam_lai_cuoc_doi	Painting Squares (IOI20_squares)	C++17	100 / 100	211 ms	728 KiB

squares

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const bool typetest = 0;
const int N = 2e3 + 5;
const int k = 10;
int dep[N], b[N];
vector<int> a;

bool dfs(int v, int d)
{
    if (d > 1000 - k + 1)
        return true;
    b[d] = v;
    dep[v] = d;
    if (!dep[v >> 1])
        if (dfs(v >> 1, d + 1))
            return true;
    if (!dep[(v >> 1) + (1 << (k - 1))])
        if (dfs((v >> 1) + (1 << (k - 1)), d + 1))
            return true;
    return false;
}

void Make(int n)
{
    for (int i = 1; i < n - k + 1; ++i)
        a[i - 1] = b[i] & 1;
    for (int i = 0; i < k; ++i)
        a[n - k + 1 + i - 1] = (b[n - k + 1] >> i) & 1;
}

vector<int> paint(int n)
{
    a.resize(n + 1);
    if (n <= k)
    {
        for (int i = 0; i < n; ++i)
            a[i] = 1;
        a[n] = k;
        return a;
    }
    fill_n(dep, N, 0);
    dfs(1, 1);
    Make(n);
    a[n] = k;
    return a;
}

int find_location(int n, vector<int> c)
{
    a.resize(n + 1);
    if (n <= k)
    {
        while (c.back() == -1)
            c.pop_back();
        return n - c.size();
    }
    fill_n(dep, N, 0);
    dfs(1, 1);
    Make(n);
    while (c.back() == -1)
        c.pop_back();
    if (c.size() < k)
        return n - c.size();
    for (int i = 0; i <= n - (int)c.size(); ++i)
    {
        bool flag(1);
        for (int j = 0; j < (int)c.size(); ++j)
            if (a[i + j] != c[j])
            {
                flag = 0;
                break;
            }
        if (flag)
            return i;
    }
    return -1;
}

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