Submission #1229962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229962		Muhammad_Aneeq	popa (BOI18_popa)	C++20	61 / 100	213 ms	464 KiB

popa

#include <iostream>
#include <algorithm>
#include <numeric>
#include "popa.h"
using namespace std;
int const MAXNN=1e3+10;
// int s[MAXNN]={};
int lc[MAXNN],rc[MAXNN],pr[MAXNN],sf[MAXNN];
// bool query(int a,int b,int c,int d)
// {
// 	int g=0,g1=0;
// 	for (int i=a;i<=b;i++)
// 		g=gcd(g,s[i]);
// 	for (int i=c;i<=d;i++)
// 		g1=gcd(g1,s[i]);
// 	return (g==g1);
// }
int sol(int l,int r)
{
	if (l>r)
		return -1;
	if (l==r)
		return l;
	for (int i=l;i<=r;i++)
	{
		if (pr[i]<=l&&sf[i]>=r)
		{
			lc[i]=sol(l,i-1);
			rc[i]=sol(i+1,r);
			return i;
		}
	}
	return -1;
}
int solve(int N,int* left,int* right)
{
	for (int i=0;i<N;i++)
		lc[i]=rc[i]=-1;
	for (int i=0;i<N;i++)
	{
		{
			int st=-1,en=i;
			while (st+1<en)
			{
				int mid=(st+en)/2;
				if (query(mid,i,i,i))
					en=mid;
				else
					st=mid;
			}
			pr[i]=en;
		}
		{
			int st=i,en=N;
			while (st+1<en)
			{
				int mid=(st+en)/2;
				if (query(i,mid,i,i))
					st=mid;
				else
					en=mid;
			}
			sf[i]=st;
		}
	}
	int rt=sol(0,N-1);
	for (int i=0;i<N;i++)
		left[i]=lc[i],right[i]=rc[i];
	return rt;
}
// int main()
// {
// 	int n;
// 	cin>>n;
// 	for (int i=0;i<n;i++)
// 		cin>>s[i];
// 	int l[n],r[n];
// 	cout<<solve(n,l,r)<<endl;
// 	for (int i=0;i<n;i++)
// 		cout<<l[i]<<' '<<r[i]<<endl;
// }

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