Submission #119396

#	Time	Username	Problem	Language	Result	Execution time	Memory
119396		shayan_p	Library (JOI18_library)	C++14	0 / 100	502 ms	892 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 _Query(vector<int>&vec){
    bool any=0;
    for(int i=0;i<sz(vec);i++)
	any|= vec[i];
    if(any==0) return 0;
    return Query(vec);
}
    /*
void Answer(vector<int>&vec){
    for(int i=0;i<sz(vec);i++)
	cout<<vec[i]<<" ";
    cout<<endl;
    }*/

int solve(int l,int r,int x,int y){
    int n=r;
    ++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 Solve(int n){
    mrk.resize(n), ans.resize(n);    
    for(int i=0;i<n;i++){
	if(sz(v[i])==2) continue;     
	int j=solve(0,n,i, sz(v[i]) ? v[i][0] : -1);
	if(j!=-1) v[j].PB(i), v[i].PB(j);
    }
    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: 0 / 19
• Subtask 2: 0 / 81