12356 - Army Buddies

[uDebug]

Since I coded in C++, I got TL when I used cout statements for this problem. However, when I switched to printf, I got AC. (Note that I was already using scanf to read data in (instead of cin).)

Update: Input / output removed after it was pointed out to be faulty. Thanks brianfry713 and mhsn06.

[mhsn06]

1 <= L <=R <= N
what is the meaning of L>R input?
3 2
They are already killed. how it could be?
2 3

[brianfry713]

v1n1t, your input is invalid.

[uDebug]

v1n1t, your input is invalid.

Thanks for bringing this to my attention. I've removed my input.

[Shahidul.CSE]

I am getting TLE with my code. Please suggest me any faster way.

Code: Select all

#include<stdio.h>
int main()
{
    int n,r,L,R,p[100003],i,j,l,fL,fR,rp,lm,rm;

    while(scanf("%d %d",&n,&rp)!=EOF)
    {
        for(i=1;i<=n;i++)
            p[i]=1;  /* initially all soldiers are alive */
        if(n==0 && rp==0)
            break;

        for(i=1;i<=rp;i++)
        {
            fL=fR=0; //Assume left and right buddies are dead and not exist
            scanf("%d %d",&L,&R);

            for(j=L;j<=R;j++) //from L to R all buddies are killed
                p[j]=0;

            if(L>1)
            {
                for(j=L-1;j>=1;j--)   // search alive left buddy from L-1 to 1
                {
                    if(p[j]>0)
                    {
                        l=j;
                        fL=1;    // as a left alive buddy found
                        break;
                    }
                }
            }
            if(R<n)
            {
                for(j=R+1;j<=n;j++)  // search alive right buddy from R+1 to n
                {
                    if(p[j]>0)
                    {
                        r=j;
                        fR=1;    // as a right alive buddy found
                        break;
                    }
                }
            }
            if(fL==0)  // if left buddy not exist
                printf("* ");
            else
                printf("%d ",l);
            if(fR==0)  // if right buddy not exist
                printf("*\n");
            else
                printf("%d\n",r);



        }
        printf("-\n");
    }
    return 0;
}

[brianfry713]

Don't read from a file.

[Shahidul.CSE]

Don't read from a file.

Actually I submitted my code not using freopen(...);
I just used it for checking input and output.

But my code getting TLE

[brianfry713]

You can answer each query in constant time.
At the start of each test case initialize two int arrays that keep track each of the S soldiers nearest living neighbor to the left and right.
For each of the B loss reports print the neighbor values from the arrays, and update (also in constant time) the left and right arrays of the new neighbors.
Total running time should be O(S + B) for each test case, your code runs in O(S * B).

[Shahidul.CSE]

Code: Select all

Accepted ! 

[brianfry713]

Code: Select all

foreach 1 <= i <= S
  left[i] = i - 1 and right[i] = i + 1

foreach of the B loss reports
  print left[L], right[R]
  left[right[R]] = left[L]
  right[left[L]] = right[R]

[Shahidul.CSE]

Code: Select all

Accepted !

[brianfry713]

Try running your code on the sample input.

[Shahidul.CSE]

To
brianfry713,
Thanks sir, got ACCEPTED

[cleiva]

Hello,

I/O functions should be a factor in here?

I have an AC solution in C++ which runs in 0.175 seconds if I use printf and scanf, but goes TLE if I use cin and cout.

What do you guys think about that?

[brianfry713]

Yes printf and scanf are faster than cin and cout.