Submission #306922

#	Time	Username	Problem	Language	Result	Execution time	Memory
306922		phathnv	Painting Squares (IOI20_squares)	C++14	0 / 100	116 ms	468 KiB

squares

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

using namespace std;

int paint(vector <int> &a){
    int n = a.size();
    int len = 2;
    int k = 1;

    a[0] = 0;
    a[1] = 1;
    while (len < n){
        for(int i = len; i < min(2 * len, n); i++)
            a[i] = a[i - len] ^ 1;
        len <<= 1;
        k++;
    }
    return k;
}

vector <int> paint(int n){
    vector <int> res(n);
    int k = paint(res);
    res.push_back(k);

    return res;
}

int find_location(int n, vector <int> c){
    int k = c.size();

    vector <int> a(n);
    assert(k == paint(a));

    int expected = 0;
    for(int x : c){
        expected <<= 1;
        if (x != -1)
            expected |= x;
    }

    int cur = 0;
    for(int i = 0; i < n + k - 1; i++){
        cur <<= 1;
        if (i < n)
            cur |= a[i];
        cur &= (1 << k) - 1;
        if (cur == expected && i >= k - 1)
            return i - k + 1;
    }

    assert(0);
    return 0;
}

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