oj.uz

Submission #61949

# Submission time Handle Problem Language Result Execution time Memory
61949 2018-07-27T06:14:26 Z 정원준(#1799) popa (BOI18_popa) C++11
61 / 100
 310 ms 760 KB 
#include "popa.h"
#include <bits/stdc++.h>
#define L long long

using namespace std;

int query(int a,int b,int c,int d);

int bin(L s,L e){
	int S=s,E=e;
	while(S<E)
	{
		int mid=(S+E)/2;
		if(query(s,e,s,mid)==1) E=mid;
		else S=mid+1;
		//printf("%d %d %d %d\n",s,e,S,E);
	}
	return S;
}

int dfs(int s,int e,int *lef,int *rig){
	//printf("%d %d\n",s,e);
	if(s>e) return -1;
	if(s==e)
	{
		lef[s]=rig[s]=-1;
		return s;
	}
	int root=bin(s,e);
	lef[root]=dfs(s,root-1,lef,rig);
	rig[root]=dfs(root+1,e,lef,rig);
	return root;
}

int solve(int N,int *left,int *right){
	int root=dfs(0,N-1,left,right);
	return root;
}

/*
int n;
int A[1010];
int l[1010],r[1010];

int gcd(int x,int y){
	if(x>y) swap(x,y);
	if(x==0) return y;
	return gcd(y-y/x*x,x);
}

int query(int a,int b,int c,int d){
	int g1=A[a];
	int g2=A[c];
	while(a<b)
	{
		a++;
		g1=gcd(g1,A[a]);
	}
	while(c<d)
	{
		c++;
		g2=gcd(g2,A[c]);
	}
	return g1==g2;
}


int main()
{
	scanf("%d",&n);
	int i;
	for(i=0;i<n;i++)
	{
		scanf("%d",&A[i]);
	}
	printf("%d\n",solve(n,l,r));
	for(i=0;i<n;i++)
	{
		printf("%d %d\n",l[i],r[i]);
	}
	
}*/

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 376 KB Output is correct
2 Correct 23 ms 440 KB Output is correct
3 Correct 6 ms 440 KB Output is correct
4 Correct 23 ms 440 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 644 KB Output is correct
2 Correct 310 ms 760 KB Output is correct
3 Correct 115 ms 760 KB Output is correct
4 Correct 247 ms 760 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 760 KB too many queries
2 Halted 0 ms 0 KB -