제출 #1268212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268212		boss_zz	도서관 (JOI18_library)	C++20	0 / 100	19 ms	1220 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){
    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 connect(ll u,ll v){
    if(G[u][v]) return ;
    G[u][v]=G[v][u]=1;
    deg[u]++;deg[v]++;
}
void Solve(int NN){
    n=NN;
    T.resize(n,0);
    if(n==1){
        ans.push_back(1);
        Answer(ans);
        return ;
    }
    rep(u,1,n){
        if(deg[u]==2) continue;
        ll l=u,r=u;
        for(ll i=9;i>=0;--i){
            if(l+(1LL<<i)>n) continue;
            if(state(u,l+(1LL<<i))==1){
                l+=(1LL<<i);
            }
        }
        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++;
        connect(u,l);
        if(r<=n) connect(u,r);
    }
    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: 0 / 19
• Subtask 2: 0 / 81