Submission #1082330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082330		GrindMachine	Painting Squares (IOI20_squares)	C++17	0 / 100	2 ms	1024 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

/*

refs:
https://codeforces.com/blog/entry/82625
https://www.baeldung.com/cs/de-bruijn-sequence (de bruijn sequence)

*/

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;

	int k = 10;
	vector<vector<pii>> adj(1<<(k-1));
	rep(u,1<<(k-1)){
		int d = 0;
		for(auto v : {u<<1,u<<1|1}){
			adj[u].pb({v%(1<<(k-1)),d});
			d++;
		}
	}

	vector<int> ord;

	auto dfs = [&](int u, auto &&dfs) -> void{
		while(!adj[u].empty()){
			auto [v,c] = adj[u].back();
			adj[u].pop_back();
			ord.pb(u<<1|c);
			dfs(v,dfs);
		}
	};

	dfs(0,dfs);

	vector<int> a(1<<k);
	rep(i,1<<k){
		int b = k-1;
		for(int j = i; b; j = (j+1)%(1<<k), --b){
			if(ord[i]&(1<<b)){
				a[j] = 1;
			}
		}
	}

	while(sz(a) > n) a.pop_back();
	a.pb(10);
    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 = 10;

    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: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55