Submission #440957

#	Time	Username	Problem	Language	Result	Execution time	Memory
440957		SorahISA	Painting Squares (IOI20_squares)	C++17	72.50 / 100	320 ms	576 KiB

squares

#include "squares.h"
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

string overall_label = "0001100110101011010001000010011001000111110101110111011111000000000001100000100111110010010110101000110100000100101100001111010011010011010100010001101000111100101010011011000011010000100001010100101100101001101000101011110101100101011010000011111111011000100001010000010111111100010101011110100000000110001010011111111111000001011001110000111100010110110001001000110000000101101001011111110101111011110111011100000010001001000111100011101110001011101110111010111111001001111111010101100101011000100011000110000101100110011000010000011100101101001111111100000101110010101101011001101110010100010111000100101010110111110010011001111111101010000110000100111111011110001100100100000000111110110000011010101001010110011001110011110001000010100011000101001111101010001110000110000011000111101111011110001111001000010100010001111100001110110111001111110101100111000011110100100010110110110110110011100010100101110001100000010110101111001001100100010001010100100010000010000110100001101001101110101111011110";
int overall_K = 20;

vector<int> paint(int N) {
    vector<int> label(N, 1);
    for (int i = 0; i < N; ++i) label[i] = overall_label[i] ^ '0';
    
    /*
    for (auto &x : label) x = rng() & 1;
    int K = 10;
    while (true) {
        set<int64_t> app;
        for (int i = 0; i+K <= N; ++i) {
            int64_t val = 0;
            for (int j = 0; j < K; ++j) val = 2*val + label[i+j];
            app.insert(val);
        }
        if (app.size() == N - K + 1) break;
        cout << "size: " << app.size() << "\n";
        ++K;
    }
    */
    
    // for (auto x : label) cout << x;
    // cout << "\n" << K << "\n";
    
    label.eb(overall_K);
    return label;
}

int find_location(int N, vector<int> C) {
    string C_str;
    int ans = N;
    for (auto x : C) {
        if (x == -1) return ans;
        C_str += to_string(x), --ans;
    }
    for (int i = 0; i+overall_K <= N; ++i) {
        if (C_str == overall_label.substr(i, overall_K)) return i;
    }
    return -1;
}

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