## 12356 - Army Buddies

Moderator: Board moderators

Omar_
New poster
Posts: 2
Joined: Sat Dec 27, 2014 12:41 am

### Re: 12356 - Army Buddies

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);
}
}``````
Last edited by brianfry713 on Tue Jan 06, 2015 5:49 am, edited 1 time in total.

Omar_
New poster
Posts: 2
Joined: Sat Dec 27, 2014 12:41 am

### Re: 12356 - Army Buddies

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
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 12356 - Army Buddies

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 )
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

rcanepa
New poster
Posts: 6
Joined: Thu Feb 26, 2015 4:59 pm

### Re: 12356 - Army Buddies

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

antonydeepak
New poster
Posts: 2
Joined: Sun Mar 08, 2015 10:25 am

### Re: 12356 - Army Buddies

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
New poster
Posts: 6
Joined: Thu Feb 26, 2015 4:59 pm

### Re: 12356 - Army Buddies

Yeah. You are right. Thanks for your feedback!

RedGreenCode
New poster
Posts: 7
Joined: Wed May 13, 2015 3:41 am
Location: Seattle, WA, USA
Contact:

### Re: 12356 - Army Buddies

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
Deliberate practice techniques for software developers -- http://www.redgreencode.com/