#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 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]);
return (gd1==gd2);
}
int ansL[1111];
int ansR[1111];
int recurse(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(lo,mid,lo,hi))
{
ans=mid; hi=mid-1;
}
else lo=mid+1;
}
int rtl = recurse(l,ans-1);
int rtr = recurse(ans+1,r);
ansL[ans] = rtl; ansR[ans] = rtr;
return ans;
}
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;
for(int i=0;i<n;i++)
{
cin>>secret[i];
}
}
int secretL[1111];
int secretR[1111];
void process_case()
{
read_input();
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';
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
process_case();
}
*/
Compilation message
/tmp/ccBlprNk.o: In function `query(int, int, int, int)':
popa.cpp:(.text+0x0): multiple definition of `query(int, int, int, int)'
/tmp/ccoWVIjT.o:grader.cpp:(.text+0x50): first defined here
collect2: error: ld returned 1 exit status
