12356 - Army Buddies

[Omar_]

i don't know why it gets TL !! anybody please help

Code: Select all

bool arr[100010];

int main()
{
    freopen("in.txt","r",stdin);
    int s, b, l, r;
    bool flag;
    scanf("%d %d",&s,&b);
    while(s!=0 && b!=0){
        fill(arr,arr+s+1,1);
        for(int i=1;i<=b;i++){
            scanf("%d %d",&l,&r);
            flag=1;
            if(l==1)
                printf("* ");
            else{
                for(int c=l-1;c>=1;c--)
                    if(arr[c]&1){
                        printf("%d ",c);
                        flag=0;
                        break;
                    }
                if(flag)
                    printf("* ");
            }
            flag=1;
            if(r==s)
                printf("*\n");
            else{
                for(int c=r+1;c<=s;c++)
                    if(arr[c]&1){
                        printf("%d\n",c);
                        flag=0;
                        break;
                    }
                if(flag)
                    printf("*\n");
            }
            for(int c=l;c<=r;c++)
                arr[c]=0;
        }
        printf("-\n");
        scanf("%d %d",&s,&b);
    }
}

[Omar_]

please help, i don't know why it gets TL ;

Code: Select all

bool arr[100010];
int main()
{
    int s, b, l, r;
    bool flag;
    scanf("%d %d",&s,&b);
    while(s!=0 && b!=0){
        fill(arr,arr+s+1,1);
        for(int i=1;i<=b;i++){
            scanf("%d %d",&l,&r);
            flag=1;
            if(l==1)
                printf("* ");
            else{
                for(int c=l-1;c>=1;c--)
                    if(arr[c]&1){
                        printf("%d ",c);
                        flag=0;
                        break;
                    }
                if(flag)
                    printf("* ");
            }
            flag=1;
            if(r==s)
                printf("*\n");
            else{
                for(int c=r+1;c<=s;c++)
                    if(arr[c]&1){
                        printf("%d\n",c);
                        flag=0;
                        break;
                    }
                if(flag)
                    printf("*\n");
            }
            for(int c=l;c<=r;c++)
                arr[c]=0;
        }
        printf("-\n");
        scanf("%d %d",&s,&b);
    }
}

[lighted]

The first input line contains two integers S and B representing respectively the number of soldiers in the attack line, and the number of loss reports ( 1 <= B <= S <= 10^5 )

Your algo complexity is ~O(B * S). It is certainly gives TLE. Read this thread to optimize your code.

[rcanepa]

Hi everyone.

I just got an AC for this problem with a time of 0.999 (almost rejected for TL). So I am looking for advices on how could I improve the performance of my code.

Code: Select all

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main(int argc, char const *argv[])
{
    int s, b, l, r;
    map<int,int> left_buddies;
    map<int,int> right_buddies;
    while ( scanf("%d %d", &s, &b) && (s != 0 && b != 0) )
    {        
        for ( int i = 1; i <= s; ++i )
        {
            left_buddies[i] = i - 1;
            right_buddies[i] = i + 1;
        }
        for ( int i = 0; i < b; ++i)
        {
            scanf("%d %d", &l, &r);
            if ( left_buddies[l] != 0 ) printf("%d ", left_buddies[l]);
            else printf("* ");
            if ( right_buddies[r] != s + 1 ) printf("%d\n", right_buddies[r]);
            else printf("*\n");
            left_buddies[right_buddies[r]] = left_buddies[l];
            right_buddies[left_buddies[l]] = right_buddies[r];
        }
        printf("-\n");
        left_buddies.clear();
        right_buddies.clear();
    }
    return 0;
}

Thanks in advance!

[antonydeepak]

You are using a map over a 1d array. In essence you are converting all O(1) into O(log n) and hence the extra cost.

[rcanepa]

Yeah. You are right. Thanks for your feedback!

[RedGreenCode]

If you're using Java for this problem and hitting the time limit, there's some good advice here about optimizing I/O: http://www.quora.com/On-UVA-12356-Java- ... ode-solved