Submission #306987

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

squares

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

using namespace std;

string s = "0000000000100001000001000100000010010001001001000000010100100001010001000101000010010100101000001010100100101010001010101010000000011010000001100100000110001000011010100001100001000110100100011001010001100011000001001101000100110010010011000101001101010100110000110011010011001100000010110100001011001000101100010010110101001011001100101100001010110100101011001010101100011010110101100000110110100011011001001101100010110110101011011001101101100000001110100000111001000011101100001110001000111010100011100110001110000100111010010011100101001110110100111000110011101011001110011100000101110100010111001001011101100101110001010111010101011100110101110000110111010011011100101101110110110111000111011101011101110000001111010000111100100011110110001111000100111101010011110011001111011100111100001011110100101111001010111101101011110001101111010110111100111011110111100000111110100011111001001111101100111110001011111010101111100110111110111011111000011111101001111110010111111011011111100011111110101111111001111111101111111111";

vector <int> paint(int n){
    vector <int> res;
    for(int i = 0; i < n; i++)
        res.push_back(s[i] - '0');
    res.push_back(10);
    return res;
}

int find_location(int n, vector <int> c){
    while (c.back() == -1)
        c.pop_back();

    if (c.size() != 10)
        return n - (int) c.size();

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

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

    return 0;
}

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