Submission #74130

#	Time	Username	Problem	Language	Result	Execution time	Memory
74130		zscoder	popa (BOI18_popa)	C++17	61 / 100	143 ms	684 KiB

popa

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "popa.h"

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

/*
int secret[1111];
int queries;
int query(int a, int b, int c, int d)
{
	int gd1=secret[a]; int gd2=secret[c];
	for(int i=a;i<=b;i++) gd1=__gcd(gd1,secret[i]);
	for(int i=c;i<=d;i++) gd2=__gcd(gd2,secret[i]);
	queries++;
	return (gd1==gd2);
}
*/

int ansL[1111];
int ansR[1111];


int recursenaive(int l, int r) //returns root;
{
	if(l>r) return -1;
	if(l==r) return l;
	int lo = l; int hi = r-1;
	int ans = r;
	while(lo<=hi)
	{
		int mid=(lo+hi)>>1;
		if(query(l,mid,l,r))
		{
			ans=mid; hi=mid-1;
		}
		else lo=mid+1;
	}
	int rtl = recursenaive(l,ans-1);
	int rtr = recursenaive(ans+1,r);
	ansL[ans] = rtl; ansR[ans] = rtr;
	return ans;
}


int recurse2(int l, int r)
{
	if(l==-1) return r;
	if(r==-1) return l;
	if(query(l,r,l,l))
	{
		//l is better
		ansR[l] = recurse2(ansR[l], r);
		return l;
	}
	else
	{
		ansL[r] = recurse2(l, ansL[r]);
		return r;
	}
}

int recurse(int l, int r)
{
	if(l>r) return -1;
	if(l==r) return l;
	int mid=(l+r)>>1;
	int r1 = recurse(l, mid);
	int r2 = recurse(mid+1,r);
	if(query(l,mid,l,r)) //r1 is the root
	{
		ansR[r1] = recurse2(ansR[r1], r2); //winner is right child of r1
		return r1;
	}
	else
	{
		ansL[r2] = recurse2(r1, ansL[r2]);
		return r2;
	}
}

int solve(int n, int *L, int *R)
{
	for(int i=0;i<n;i++) ansL[i]=ansR[i]=-1;
	int rt = recurse(0,n-1);
	for(int i=0;i<n;i++)
	{
		L[i] = ansL[i]; R[i] = ansR[i];
	}
	return rt;
}

/*
int n; 
void read_input()
{
	//cin>>n;
	n=1000;
	for(int i=0;i<n;i++)
	{
		secret[i]=1;
		//cin>>secret[i];
	}
}

int secretL[1111];
int secretR[1111];

void process_case()
{
	read_input(); queries=0;
	int rt = solve(n, secretL, secretR);
	cerr<<"ROOT : "<<secret[rt]<<'\n';
	for(int i=0;i<n;i++)
	{
		cerr<<secret[i]<<' '<<(secretL[i]==-1?-1:secret[secretL[i]])<<' '<<(secretR[i]==-1?-1:secret[secretR[i]])<<'\n';
	}
	cerr<<"QUERIES USED : "<<queries<<'\n';
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	process_case();	
}	
*/

• Subtask 1: 37 / 37
• Subtask 2: 24 / 24
• Subtask 3: 0 / 39