Submission #1082299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082299		GrindMachine	Painting Squares (IOI20_squares)	C++17	97.25 / 100	90 ms	772 KiB

squares

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "squares.h"

std::vector<int> paint(int n) {
	// std::vector<int> labels(n + 1, 1);
	// return labels;
    
    string res = "1010101110001111000111011110110000011111010011100110111000001110001000010110000101101110011001100010110101001011000001011110110110010000010100011100111000101111110001100010001100111100000001000001000100111110010001111110010010101000101001110111110010101011101110001101000001110110111110100011110011111110101010001101101111010101101111110100101111100110101000100000010101100001110000010011010000100011110100100010010111000101001010010011001001110000111010010101010011011000010000000000011010001011110010011110110101101010101101011110001101111111110011001010111001011110000110110001100101110110101000001100100011000010100000011001110100000010010110101100110110011001111100001001100110111100000110111001000101100101000100100011101011111011011101000011010011101011001001100011010110001010110100100000001111001000011110101001001001101101011101001100101100111101011110111111101100011100101011001011010001001101110110110110100111101000010101110101000010111011110011000010010000110000111110011101100010011100"; // found by simulated annealing
    vector<int> a(n+1);
    rep(i,n) a[i] = res[i]-'0';
    a[n] = 11;
    return a;
}

int find_location(int n, std::vector<int> c) {
    string res = "1010101110001111000111011110110000011111010011100110111000001110001000010110000101101110011001100010110101001011000001011110110110010000010100011100111000101111110001100010001100111100000001000001000100111110010001111110010010101000101001110111110010101011101110001101000001110110111110100011110011111110101010001101101111010101101111110100101111100110101000100000010101100001110000010011010000100011110100100010010111000101001010010011001001110000111010010101010011011000010000000000011010001011110010011110110101101010101101011110001101111111110011001010111001011110000110110001100101110110101000001100100011000010100000011001110100000010010110101100110110011001111100001001100110111100000110111001000101100101000100100011101011111011011101000011010011101011001001100011010110001010110100100000001111001000011110101001001001101101011101001100101100111101011110111111101100011100101011001011010001001101110110110110100111101000010101110101000010111011110011000010010000110000111110011101100010011100"; // found by simulated annealing
    vector<int> a(n);
    rep(i,n) a[i] = res[i]-'0';
   	int k = 11;

    int cnt = count(all(c),-1);
   	if(cnt){
   		return n+cnt-k;
   	}

   	rep(i,n){
   		if(i+k-1 >= n) break;
   		bool ok = true;
   		rep(j,k){
   			if(a[i+j] != c[j]){
   				ok = false;
   				break;
   			}
   		}

   		if(ok){
   			return i;
   		}
   	}

   	assert(0);
   	return -1;
}

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