Submission #1268201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268201		boss_zz	Library (JOI18_library)	C++20	19 / 100	125 ms	5064 KiB

library

#include<bits/stdc++.h>
#include "library.h"
#define rep(a,b,c) for(ll a=b;a<=c;++a)
#define ll long long 
#define ff first 
#define ss second 
#define mp make_pair 
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
using namespace std;
const ll N=1005,inf=1e18;
ll n,G[N][N],deg[N],head;
vector<int> T,ans;
bitset<N> flag;
ll nxt(ll u){
    rep(v,1,n) if(!flag[v]&&G[u][v]) return v;
    return 0;
}
bool check(){
    rep(i,0,n-1) if(T[i]) return true;
    return false;
}
ll state(ll u,ll x){
    if(x>n) return 1;
    rep(i,1,x) if(i!=u) T[i-1]=1;
    ll a=(check()? Query(T):0);
    T[u-1]=1;
    ll b=Query(T);
    T[u-1]=0;
    rep(i,1,x) T[i-1]=0;
    return b-a;
}
void Solve(int NN){
    n=NN;
    T.resize(n,0);
    if(n==1){
        ans.push_back(1);
        Answer(ans);
        return ;
    }
    rep(u,1,n){
        ll l=0,r=0;
        for(ll i=9;i>=0;--i){
            if(l+(1LL<<i)>n) continue;
            if(state(u,l+(1LL<<i))==1){
                l+=(1LL<<i);
            }
        }
        r=l+1;
        for(ll i=9;i>=0;--i){
            if(r+(1LL<<i)>n) continue;
            if(state(u,r+(1LL<<i))>=0){
                r+=(1LL<<i);
            }
        }
        l++;
        r++;
        G[u][l]=G[l][u]=1;deg[u]++;
        if(r!=n+1) G[u][r]=G[r][u]=1,deg[u]++;
    }
    rep(i,1,n) if(deg[i]==1) head=i;
    ll u=head;
    while(ans.size()<n){
        ans.push_back(u);
        flag[u]=1;
        u=nxt(u);
    }
    Answer(ans);
}

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