Submission #1169194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169194		jerzyk	Painting Squares (IOI20_squares)	C++20	100 / 100	27 ms	420 KiB

squares

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1000;
const int K = 10;
bool czyinit = 0;
string s = "0000000000100000000110000000101000000011100000010010000001011000000110100000011110000010001000001001100000101010000010111000001100100000110110000011101000001111100001000010001100001001010000100111000010100100001010110000101101000010111100001100010000110011000011010100001101110000111001000011101100001111010000111111000100010100010001110001001001000100101100010011010001001111000101001100010101010001010111000101100100010110110001011101000101111100011000110010100011001110001101001000110101100011011010001101111000111001100011101010001110111000111100100011110110001111101000111111100100100110010010101001001011100100110110010011101001001111100101001010011100101010110010101101001010111100101100110010110101001011011100101110110010111101001011111100110011010011001111001101010100110101110011011011001101110100110111110011100111010110011101101001110111100111101010011110111001111101100111111010011111111010101010111010101101101010111110101101011011110101110111010111101101011111110110110111011011111101";
int wh[(1<<(K + 1))];

vector<int> paint(int n)
{
    vector<int> ans;
    for(int i = 0; i < n; ++i)
        ans.pb(s[i] - '0');
    ans.pb(K);
    return ans;
}

void init()
{
    czyinit = 1;
    //cerr << s.size() << "\n";
    for(int i = 0; i <= N - K; ++i)
    {
        int cur = 0;
        for(int j = 0; j < K; ++j)
            cur += (1<<j) * (int)(s[i + j] - '0');
        wh[cur] = i;
    }
}

int find_location(int n, vector<int> c)
{
    if(!czyinit) init();
    if(c.back() == -1)
    {
        while(c.back() == -1)
            c.pop_back();
        return n - (int)c.size();
    }
    int cur = 0;
    for(int i = 0; i < (int)c.size(); ++i)
        cur += (1<<i) * c[i];
    return wh[cur];
}

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