Submission #119401

#	Time	Username	Problem	Language	Result	Execution time	Memory
119401		shayan_p	Library (JOI18_library)	C++14	100 / 100	552 ms	564 KiB

library

// High above the clouds there is a rainbow...

#include "library.h"

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1010,mod=1e9+7;
const ll inf=1e18;

vector<int> v[maxn], mrk, ans;
int n;

int _Query(vector<int>&vec){
    bool any=0;
    for(int i=0;i<sz(vec);i++)
	any|= vec[i];
    if(any==0) return 0;
    /*   for(int i=0;i<sz(vec);i++)
	cout<<vec[i]<<" ";
    cout<<endl;
    int x; cin>>x;
    return x;*/
    return Query(vec);
}
/*
void Answer(vector<int>&vec){
    for(int x:vec)
	cout<<x<<" ";
    cout<<endl;
}
*/
int solve(int l,int r,int x,int y){
    ++r;
    while(r-l>1){
	int mid=(l+r)>>1;
	for(int i=0;i<n;i++)
	    mrk[i]=0;
	int cnt=0;
	for(int i=l;i<mid;i++)
	    mrk[i]= i!=x && i!=y, cnt+= i!=x && i!=y;
	int A=cnt- _Query(mrk);
	mrk[x]=1;
	int B=cnt+1- _Query(mrk);
	if(A==B) l=mid;
	else r=mid;
    }
    if(l==n) return -1;
    return l;
}

void dfs(int u,int par=-1){
    int y= solve(0,n,u,par);
    if(y!=-1) v[u].PB(y), v[y].PB(u), dfs(y,u);
}

void Solve(int N){
    n=N;
    mrk.resize(n), ans.resize(n);

    if(n==1){
	ans[0]=1;
	Answer(ans);
	return;
    }
    
    dfs(0), dfs(0, v[0][0]);
    for(int i=0;i<n;i++){
	mrk[i]=0;
    }
    for(int i=0;i<n;i++){
	if(sz(v[i])==1){
	    int cnt=0;
	    int tmp=i;
	    while(cnt<n){
		ans[cnt++]=tmp+1;
		mrk[tmp]=1;
		
		int nxt=-1;
		for(int j:v[tmp]){
		    if(mrk[j]==0) assert(nxt==-1), nxt=j;
		}
		tmp=nxt;
	    }
	    break;
	}
    }
    Answer(ans);
}
/*
int main(){
    int n; cin>>n;
    Solve(n);
    return 0;
}
*/

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