oj.uz

답안 #367583

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
367583 2021-02-17T17:25:02 Z rocks03 Painting Squares (IOI20_squares) C++14
100 / 100
 380 ms 724 KB 
//#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 306 ms 716 KB Output is correct
2 Correct 380 ms 688 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 277 ms 724 KB Output is correct
2 Correct 363 ms 724 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 274 ms 724 KB Output is correct
2 Correct 367 ms 724 KB Output is correct

Subtask #4
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 210 ms 676 KB Output is correct
2 Correct 289 ms 656 KB Output is correct