Submission #367583

#	Time	Username	Problem	Language	Result	Execution time	Memory
367583		rocks03	Painting Squares (IOI20_squares)	C++14	100 / 100	380 ms	724 KiB

squares

//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include "squares.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 1000+100;
char A[] = {'0', '1'};
int vis[MAXN];
vector<int> edges;

const int MAXK = 10;
void dfs(int v){
    rep(k, 0, 2){
        int u = ((v << 1) & ((1 << MAXK) - 1)) + A[k];
        assert(u >= 0 && u < MAXN);
        if(!vis[u]){
            vis[u] = true;
            u &= ((1 << MAXK) - 1);
            dfs(u);
            edges.pb(k);
        }
    }
}

bool done = false;
string de_bruijn;

void init(){
    memset(vis, false, sizeof(vis));
    edges.clear();
    int start = 0;
    dfs(start);
    de_bruijn.clear();
    rep(i, 0, (1 << MAXK)){
        de_bruijn += A[edges[i]];
    }
}

vector<int> paint(int n){
    // construct de bruijn sequence
    init();
    vector<int> v(n);
    rep(i, 0, n){
        v[i] = de_bruijn[i] - '0';
    }
    int K = min(10, n);
    v.pb(K);
    return v;
}

int find_location(int n, vector<int> c){
    int f = 0;
    for(int x : c){
        f += (x == -1);
    }
    if(f){
        return (n - (SZ(c) - f));
    }
    init();
    int p = 1;
    for(int x : c){
        f += p * x;
        p <<= 1;
    }
    int K = min(10, n);
    rep(i, 0, n){
        if(i + K <= n){
            int hsh = 0;
            rep(j, i, i + K){
                hsh += ((de_bruijn[j] - '0') << (j - i));
            }
            if(f == hsh)
                return i;
        }
    }
  	assert(false);
}

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