I want to know what is wrong with my logic:
Question: Link
My submission:
#include<bits/stdc++.h>
using namespace std;
#define int long long
void fastscan(int &number)
{
bool negative = false;
register int c;
number = 0;
c = getchar();
if (c=='-')
{
negative = true;
c = getchar();
}
for (; (c>47 && c<58); c=getchar())
number = number *10 + c - 48;
if (negative)
number *= -1;
}
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.in", " r", stdin);
freopen("output.in", "w", stdout);
freopen("error.in","w",stderr);
#endif
int t;
fastscan(t);
while (t--)
{
int n;
fastscan(n);
int A[n],prefix[n];
for(int i=0;i<n;i++)
fastscan(A[i]);
int **eo=new int*[n];
int sum=0;
for(int i=0;i<n;i++)
{
sum+=A[i];
prefix[i]=sum;
eo[i]=new int[2];
eo[i][0]=0;
eo[i][1]=0;
}
eo[0][0]+=((A[0]%2==0)?1:0);
eo[0][1]+=((A[0]%2!=0)?1:0);
for(int i=1;i<n;i++)
{
eo[i][0]+=((A[i]%2==0)?1:0);
eo[i][1]+=((A[i]%2!=0)?1:0);
eo[i][0]+=eo[i-1][0];
eo[i][1]+=eo[i-1][1];
}
// map<int,vi> m;
unordered_map<int,vector<int>,custom_hash> m;
for(int i=0;i<n;i++)
{
m[A[i]].push_back(i);
}
int ans=0;
for(auto x:m)
{
if (x.second.size()>1)
{
vector<int> indexes=x.second;
for(int i=0;i<indexes.size()-1;i++)
{
int counteven=eo[indexes[i+1]][0]-eo[indexes[i]][0]-((A[indexes[i+1]]%2==0)?1:0);
int countodd=eo[indexes[i+1]][1]-eo[indexes[i]][1]-((A[indexes[i+1]]%2!=0)?1:0);
if (A[indexes[i]]%2==0 && counteven%2==0)
{
int currsum=prefix[indexes[i+1]]-prefix[indexes[i]]-A[indexes[i+1]];
// trace3(indexes[i],indexes[i+1],currsum);
ans=max(ans,currsum);
}
else if (A[indexes[i]]%2!=0 && countodd%2!=0)
{
int currsum=prefix[indexes[i+1]]-prefix[indexes[i]]-A[indexes[i+1]];
// trace3(indexes[i],indexes[i+1],currsum);
ans=max(ans,currsum);
}
}
}
}
cout<<ans<<endl;
}
return 0;
}
I have added these optimisation because my code was giving TLE
Can someone please help!!