Source code for submission s1250

Go to diff to previous submission

#include <iomanip>
#include <iostream>
#include <cstdlib>
#include <cstdio>
//#include <stdlib.h>
 
using namespace std;
struct elem{
int idx;
int dir;
}; 
 
int cmp(const void * x, const void * y){
elem *t1 = (elem*) x;
elem *t2 = (elem*) y;
return (t1->idx) - (t2->idx);
}
 
 
int main(){
int number,length;
 
scanf("%d %d", &length, &number);
int *start_pos = new int[number];
int *act_pos = new int[number];
 
elem *pole = new elem [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;
		pole[i].dir=1;
 
	}
	else {
		len[i]=pos;
		dir[i]=-1;
		pole[i].dir=-1;
	}
	pole[i].idx=pos;
	start_pos[i]=pos;
	act_pos[i]=pos;
}
 
 
 
 
 
 
 
// 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;
}
 
 
int number2=number;
qsort(pole, number, sizeof(elem), cmp);
number=number2;
 
 
for  (int i=0; i < number; i++){
	act_pos[i]=start_pos[i]=pole[i].idx;
	dir[i]=pole[i].dir;
 
}
 
 
if (number > 1)
for (int k=0; k < max-1; k++){
//cout << "-------------" << endl;
//cout << "time: " << k  << endl;
 
for  (int i=0; i < number; i++)
	preMoved[i]=false;
 
//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){
//		cout << "ant " << i << " is on pos " << act_pos[i] << endl;
		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;
			}
		}
	}
}
 
}
 
 
int dfas=0;
for  (int i=0; i < number; i++)
	if (alive[i]==true){
//		cout << i << " is alive" << " on start pos" << start_pos[i] <<  endl;
	fin[dfas++]=i;
	}
//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;
}
 
 

Diff to submission s1038

--- c4.s1038.cteam015.ants.cpp.0.ants.cpp
+++ c4.s1250.cteam015.ants.cpp.0.ants.cpp
@@ -3,6 +3,18 @@
 #include <cstdlib>
 #include <cstdio>
+//#include <stdlib.h>
 
 using namespace std;
+struct elem{
+int idx;
+int dir;
+}; 
+
+int cmp(const void * x, const void * y){
+elem *t1 = (elem*) x;
+elem *t2 = (elem*) y;
+return (t1->idx) - (t2->idx);
+}
+
 
 int main(){
@@ -12,4 +24,7 @@
 int *start_pos = new int[number];
 int *act_pos = new int[number];
+
+elem *pole = new elem [number];
+
 int *dir = new int[number];
 for  (int i=0; i < number; i++)
@@ -23,7 +38,8 @@
         char tmp;
         scanf("%d %c", &pos, &tmp);
-        if  (tmp == 'R' ){
+       if  (tmp == 'R' ){
                 len[i]=length-pos;
                 dir[i]=1;
+                pole[i].dir=1;
                 
         }
@@ -31,26 +47,11 @@
                 len[i]=pos;
                 dir[i]=-1;
+                pole[i].dir=-1;
         }
+        pole[i].idx=pos;
         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;
-                }
-                        
-        }
-}
 
 
@@ -99,14 +100,31 @@
 }
 
+
+int number2=number;
+qsort(pole, number, sizeof(elem), cmp);
+number=number2;
+
+
+for  (int i=0; i < number; i++){
+        act_pos[i]=start_pos[i]=pole[i].idx;
+        dir[i]=pole[i].dir;
+
+}
+
+
+if (number > 1)
 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; i++)
+        preMoved[i]=false;
+
+//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;
+//              cout << "crash 1 ants " << i << " and " << i+1 << " on pos " <<  act_pos[i] << "(+1)" << endl;
                 preMoved[i]=true;
                 dir[i]*=-1;
@@ -119,8 +137,10 @@
 // move
 for  (int i=0; i < number; i++){
-        if (preMoved[i]==true)
+        if (preMoved[i]==true){
+//              cout << "ant " << i << " is on pos " << act_pos[i] << endl;
                 continue;
+        }
         act_pos[i]+=dir[i];
-        //cout << "ant " << i << " is on pos " << act_pos[i] << endl;
+//      cout << "ant " << i << " is on pos " << act_pos[i] << endl;
 }
 
@@ -130,5 +150,5 @@
                 alive[i]=false;
                 aliveAnts--;
-                //cout << "ant " << i << " died on pos " << act_pos[i] << endl;
+//              cout << "ant " << i << " died on pos " << act_pos[i] << endl;
         }
 }
@@ -152,5 +172,5 @@
                         if (act_pos[j]==i){
                                 dir[j]*=-1;     
-                                //cout << "changing dir of ant " << j << " into "        << dir[j] << endl;
+//                              cout << "changing dir of ant " << j << " into "  << dir[j] << endl;
                         }
                 }
@@ -161,4 +181,10 @@
 
 
+int dfas=0;
+for  (int i=0; i < number; i++)
+        if (alive[i]==true){
+//              cout << i << " is alive" << " on start pos" << start_pos[i] <<  endl;
+        fin[dfas++]=i;
+        }
 //cout << "before output" << endl;