oj.uz

Submission #119401

# Submission time Handle Problem Language Result Execution time Memory
119401 2019-06-21T07:36:17 Z shayan_p Library (JOI18_library) C++14
100 / 100
 552 ms 564 KB 
// 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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 384 KB # of queries: 2964
2 Correct 28 ms 424 KB # of queries: 2946
3 Correct 46 ms 352 KB # of queries: 3105
4 Correct 54 ms 256 KB # of queries: 3106
5 Correct 55 ms 256 KB # of queries: 3105
6 Correct 48 ms 376 KB # of queries: 3106
7 Correct 38 ms 256 KB # of queries: 3106
8 Correct 51 ms 384 KB # of queries: 2980
9 Correct 45 ms 344 KB # of queries: 3087
10 Correct 32 ms 256 KB # of queries: 1829
11 Correct 2 ms 256 KB # of queries: 0
12 Correct 2 ms 256 KB # of queries: 7
13 Correct 2 ms 256 KB # of queries: 12
14 Correct 2 ms 384 KB # of queries: 22
15 Correct 2 ms 256 KB # of queries: 127
16 Correct 4 ms 256 KB # of queries: 273

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 384 KB # of queries: 2964
2 Correct 28 ms 424 KB # of queries: 2946
3 Correct 46 ms 352 KB # of queries: 3105
4 Correct 54 ms 256 KB # of queries: 3106
5 Correct 55 ms 256 KB # of queries: 3105
6 Correct 48 ms 376 KB # of queries: 3106
7 Correct 38 ms 256 KB # of queries: 3106
8 Correct 51 ms 384 KB # of queries: 2980
9 Correct 45 ms 344 KB # of queries: 3087
10 Correct 32 ms 256 KB # of queries: 1829
11 Correct 2 ms 256 KB # of queries: 0
12 Correct 2 ms 256 KB # of queries: 7
13 Correct 2 ms 256 KB # of queries: 12
14 Correct 2 ms 384 KB # of queries: 22
15 Correct 2 ms 256 KB # of queries: 127
16 Correct 4 ms 256 KB # of queries: 273
17 Correct 440 ms 564 KB # of queries: 19975
18 Correct 498 ms 524 KB # of queries: 19734
19 Correct 542 ms 504 KB # of queries: 19974
20 Correct 370 ms 364 KB # of queries: 18697
21 Correct 369 ms 516 KB # of queries: 17622
22 Correct 471 ms 552 KB # of queries: 19974
23 Correct 509 ms 532 KB # of queries: 19952
24 Correct 141 ms 484 KB # of queries: 9261
25 Correct 492 ms 424 KB # of queries: 19511
26 Correct 445 ms 496 KB # of queries: 18280
27 Correct 116 ms 344 KB # of queries: 9216
28 Correct 457 ms 500 KB # of queries: 19208
29 Correct 552 ms 504 KB # of queries: 19186
30 Correct 506 ms 536 KB # of queries: 19208