Submission #440959

#	Time	Username	Problem	Language	Result	Execution time	Memory
440959		SorahISA	Painting Squares (IOI20_squares)	C++17	83.50 / 100	312 ms	508 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 = "1111101111111011000111111110100111100100000010001001000010011000011100100010111101011111010100100001011000111110001111001000100011110110111110011010001011111001101011011000011111110111010110010011101101010000100110111000110010000010110000011010000100000100111001110010000000001001110100111101011011010110000010010010100101110110111001101001101100111100001000100110100100001100010111010001111100001011011110000101100011000000111010001000000110000110011011101111110001000100110000101100110010001010001001001011110111001110111001101010110110101111100111111011000001001011110000000101101001010011110001001000001010001111111010000000011011110111100010110010010101000101001001101011001010011011011001001000010100000100010001111001110100011100001100001010110110101001001010011111100010110110111000011011100101110111110111010011000000001011010111001101000010110110100001011110011111010011110110110100101010011101100100011000110011000011011110101111100001100110011011000111101100101101100100110100010100010000";
int overall_K = 16;

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;
        ++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: 38.5 / 55