ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
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;

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

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

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

        while ((a[ma]==b[mb])&&(b[mb]==c[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)))