Page 2 of 2

### Re: 12356 - Army Buddies

Posted: Sat Dec 27, 2014 12:44 am

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);
}
}``````

### Re: 12356 - Army Buddies

Posted: Sat Dec 27, 2014 12:47 am

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);
}
}``````

### Re: 12356 - Army Buddies

Posted: Tue Dec 30, 2014 9:01 am
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 )

### Re: 12356 - Army Buddies

Posted: Fri Feb 27, 2015 7:59 pm
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;
}
``````

### Re: 12356 - Army Buddies

Posted: Sun Mar 08, 2015 10:28 am
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.

### Re: 12356 - Army Buddies

Posted: Sun Mar 08, 2015 5:04 pm
Yeah. You are right. Thanks for your feedback!

### Re: 12356 - Army Buddies

Posted: Wed May 13, 2015 7:58 am
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