oj.uz

Submission #306922

# Submission time Handle Problem Language Result Execution time Memory
306922 2020-09-26T14:29:54 Z phathnv Painting Squares (IOI20_squares) C++14
0 / 100
 116 ms 468 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 468 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 432 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 468 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 468 KB Incorrect
2 Halted 0 ms 0 KB -