Submission #367552

#	Time	Username	Problem	Language	Result	Execution time	Memory
367552		rocks03	Painting Squares (IOI20_squares)	C++14	0 / 100	132 ms	708 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;

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

bool done = false;
string de_bruijn;
map<int, int> mp[10 + 1];

void init(){
    if(done) return; done = true;
    int start = 0;
    dfs(start);
    rep(i, 0, (1 << K)){
        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';
    }
    K = min(10, n);
    rep(i, 0, n){
        if(i + K <= n){
            int hsh = 0;
            rep(j, i, i + K){
                hsh += (v[j] << (j - i));
            }
            mp[K][hsh] = i;
        }
    }
    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));
    }
    int p = 1;
    for(int x : c){
        f += p * x;
        p <<= 1;
    }
    return mp[SZ(c)][f];
}

Compilation message (stderr)

squares.cpp: In function 'void init()':
squares.cpp:42:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   42 |     if(done) return; done = true;
      |     ^~
squares.cpp:42:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   42 |     if(done) return; done = true;
      |                      ^~~~

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