Submission #1082331

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

/*

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) {
	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();
	
    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: 55 / 55