Submission #1164581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164581		Sang	Library (JOI18_library)	C++20	0 / 100	106 ms	1416 KiB

library

#ifndef _Pbrngw_
#include "library.h"
#endif // _Pbrngw_
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

int n;
bool block[N];
deque<int> dq;

int Query(const std::vector<int>& M);
void Answer(const std::vector<int>& res);

bool check(int x, int y, int i){
    FOR (j, 0, i){
        int c = (x>>j)&1;
        int c2 = (y>>j)&1;
        if (c == c2) continue;
        return 0;
    }
    return 1;
}

void findNxt(int u, bool frt){
    int x = 0;
    vector<int> M(n, 0);
    FOR (i, 0, 9){
        int ok = 0;
        FOR (j, 1, n){
            if (block[j]) continue;
            if (check(x, j, i)) M[j-1] = 1, ok = 1;
        }
        if (ok ==0){
            x += (1<<i);
        } else {
            int cur = Query(M);
            M[0] = 1;
            if (cur < Query(M)){
                x += (1<<i);
            }
        }
    }
    if (x > n) return;
    if (frt) dq.push_front(x);
    else dq.pb(x);
    findNxt(x, frt);
}

void Solve(int _n){
    n = _n;
    vector<int> M(n, 0), res(n, 0);
    if (n <= 2){
        FOR (i, 0, n - 1) res[i] = i + 1;
        Answer(res);
        return;
    }

    dq.pb(1);
    block[1] = 1;
    int x = 0;
    FOR (i, 0, 9){
        int ok = 0;
        FOR (j, 1, n){
            if (block[j]) continue;
            if (check(x, j, i)) M[j-1] = 1, ok = 1;
        }
        if (ok ==0){
            x += (1<<i);
        } else {
            int cur = Query(M);
            M[0] = 1;
            if (cur < Query(M)){
                x += (1<<i);
            }
        }
    }
    assert(x <= n);
    block[x] = 1;
    dq.push_front(x);
    findNxt(x, 1);
    findNxt(1, 0);
    FOR (i, 0, n - 1) res[i] = dq[i];
    Answer(res);
}

#ifdef _Pbrngw_
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    return 0;
}

#endif // _Pbrngw_

• Subtask 1: 0 / 19
• Subtask 2: 0 / 81