Submission #371624

#	Time	Username	Problem	Language	Result	Execution time	Memory
371624		Lam_lai_cuoc_doi	Painting Squares (IOI20_squares)	C++17	0 / 100	1 ms	672 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 = 1e3 + 5;
map<int, int> ck;
int a[N], m, s, ans, b[N];

bool dfs(int v, int dep)
{
    ck[v] = dep;
    b[dep - 1] = v;
    if (dep == 971)
        return true;
    int u = v >> 1;
    if (!ck[u + (1 << 29)])
        if (dfs(u + (1 << 29), dep + 1))
            return true;
    if (!ck[u])
        if (dfs(u, dep + 1))
            return true;
    return false;
}

int *paint(int n)
{
    if (n <= 30)
    {
        for (int i = 0; i < n; ++i)
            a[i] = 1;
        a[n] = n;
        return a;
    }
    ck.clear();
    dfs(1, 1);
    for (int i = 1; i < n - 30 + 1; ++i)
        a[i - 1] = b[i - 1] & 1;
    for (int i = 0; i < 30; ++i)
        a[n - 30 + 1 + i - 1] = (b[n - 30 + 1 - 1] >> i) & 1;
    a[n] = 30;
    return a;
}

int find_location(int n, vector<int> c)
{
    if (n <= 30)
    {
        for (int i = 0; i < n; ++i)
            if (c[i] != 1)
                return -1;
        return 0;
    }
    ck.clear();
    dfs(1, 1);
    ans = -1;
    for (int i = 1; i <= n - 30 + 1; ++i)
    {
        bool flag(0);
        for (int j = 0; j < 30; ++j)
            if (c[j] != a[i - 1 + j])
            {
                flag = 1;
                break;
            }
        if (!flag)
        {
            ans = i - 1;
            break;
        }
    }
    return ans;
}

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