ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1880. Psych Up's Eigenvalues

How to get AC 0.015?
Posted by PrankMaN 21 Mar 2013 23:37
I've seen few people got AC in 0.015 seconds, but how? I used binary search and each iteration's left border started from the last found number, but not from the beginning of array and got 0.031 seconds.
Re: How to get AC 0.015?
Posted by lightstone 5 May 2013 21:43
binary search gives n*log^2(n) and its possible to solve this in 3*n if you walk the array with least number on each step and wait until all 3 pointed are same to increase count;
I have 0.031 too but i`m sure it is possible to optimize my code (e.g. i`ve placed too many checkers if the array is fully passed)

int main()
{
int ma=0,mb=0,mc=0,an,bn,cn,a[4000],b[4000],c[4000],sum=0;

scanf("%d",&an);
for(int i=0;i<an;++i) scanf("%d",&a[i]);

scanf("%d",&bn);
for(int i=0;i<bn;++i) scanf("%d",&b[i]);

scanf("%d",&cn);
for(int i=0;i<cn;++i) scanf("%d",&c[i]);

do
{
while ((a[ma]==b[mb])&&(b[mb]==c[mc]))
{
++sum;
++ma;
++mb;
++mc;
if((ma>=an)||(mb>=bn)||(mc>=cn)) break;
}
if((ma>=an)||(mb>=bn)||(mc>=cn)) break;

if(a[ma]==min(min(b[mb],c[mc]),a[ma])) ++ma;
else if(b[mb]==min(min(b[mb],c[mc]),a[ma])) ++mb;
else if(c[mc]==min(min(b[mb],c[mc]),a[ma])) ++mc;

if((ma>=an)||(mb>=bn)||(mc>=cn)) break;
} while(1);

printf("%d", sum);
return 0;
}
Re: How to get AC 0.015?
Posted by Ivan Metelev 19 Nov 2014 15:53
You use Python. There is many useful functions))) My program took only 4 lines)))