ants.cpp

#include <iomanip>
#include <iostream>
#include <cstdlib>
#include <cstdio>
 
using namespace std;
 
int main(){
int number,length;
 
scanf("%d %d", &length, &number);
int *start_pos = new int[number];
int *act_pos = new int[number];
int *dir = new int[number];
for  (int i=0; i < number; i++)
	start_pos[i]=0;
 
int *len=new int[number];
int pos;
 
// read all inputs && count time for each ant
for  (int i=0; i < number; i++){
	char tmp;
	scanf("%d %c", &pos, &tmp);
	if  (tmp == 'R' ){
		len[i]=length-pos;
		dir[i]=1;
 
	}
	else {
		len[i]=pos;
		dir[i]=-1;
	}
	start_pos[i]=pos;
	act_pos[i]=pos;
}
 
for  (int i=0; i < number; i++){
	int max=start_pos[0];
	for  (int j=0; j < number-1-i; j++){
		if (start_pos[i] > max){
			int tmp=start_pos[i];
			start_pos[i]=start_pos[i+1];
			start_pos[i+1]=tmp;
			tmp= act_pos[i];
			act_pos[i]=act_pos[i+1];
			act_pos[i+1]=tmp;
			tmp= dir[i];
			dir[i]=dir[i+1];
			dir[i+1]=tmp;
		}
 
	}
}
 
 
 
 
 
 
// find max
int max = len[0];
for  (int i=1; i < number; i++){
	if (len[i] > max){
		max = len[i];
	}
}
 
//cout << "max found" << endl;
 
int *fin = new int [number];
for  (int i=0; i < number; i++)
	if (len[i] == -1);
 
 
int nr=0;
for  (int i=0; i < number; i++){
	if (len[i] == max){
		fin[nr++]=i;
	}
}
 
 
int *used_pos = new int [length];
for  (int i=0; i < number; i++)
	used_pos[i]=0;
 
bool *alive = new bool [number];
int aliveAnts=number;
bool *preMoved = new bool [number];
 
int *id = new int [number];
 
// setup
for  (int i=0; i < number; i++){
	alive[i]=true;
	preMoved[i]=false;
	id[i]=i;
}
 
for (int k=0; k < max-1; k++){
//cout << "-------------" << endl;
//cout << "time: " << k  << endl;
 
// distance = 1, direction = crash ===> change direction, do NOT change actual position!
for  (int i=0; i < number-1; i++){
	if ((alive[i]==false)||(alive[i+1]==false))
		continue;
	if ((act_pos[i]+dir[i]==(act_pos[i+1])) && ((act_pos[i])==(act_pos[i+1]+dir[i+1]))){
		//cout << "crash 1 ants " << i << " and " << i+1 << " on pos " <<  act_pos[i] << "(+1)" << endl;
		preMoved[i]=true;
		dir[i]*=-1;
		preMoved[i+1]=true;
		dir[i+1]*=-1;
	}
}
 
 
// move
for  (int i=0; i < number; i++){
	if (preMoved[i]==true)
		continue;
	act_pos[i]+=dir[i];
	//cout << "ant " << i << " is on pos " << act_pos[i] << endl;
}
 
// check for death ants
for  (int i=0; i < number; i++){
	if ((alive[i]==true)&&((act_pos[i]>=length)||(act_pos[i]<0))){
		alive[i]=false;
		aliveAnts--;
		//cout << "ant " << i << " died on pos " << act_pos[i] << endl;
	}
}
 
 
for  (int i=0; i < length; i++){
	used_pos[i]=0;
}
 
// distance = 2, direction = crash
for  (int i=0; i < number; i++){
	if (alive[i]==false)
		continue;		
	used_pos[act_pos[i]]++;
}
 
// if on 'same' pos => crash => change direction
for  (int i=0; i < length; i++){
	if (used_pos[i] > 1){
		for (int j=0; j < number; j++){
			if (act_pos[j]==i){
				dir[j]*=-1;	
				//cout << "changing dir of ant " << j << " into "	 << dir[j] << endl;
			}
		}
	}
}
 
}
 
 
//cout << "before output" << endl;
 
 
 
cout << "The last ant will fall down in " << max << " seconds -" << " started at " << start_pos [fin[0]];
 
for (int i=1; i < nr; i++){
cout << " and " << start_pos [fin[i]];
}
 
cout << "."<<endl;
 
return 0;
}