Source code for submission s1357

ants.cpp

  1. #include<iostream>
  2.  
  3. #include<vector>
  4. #include<algorithm>
  5. #include<map>
  6. #include<set>
  7. #include<list>
  8. #include<stack>
  9. #include<queue>
  10.  
  11. #include<stdio.h>
  12. #include<stdlib.h>
  13. #include<math.h>
  14. #include<string.h>
  15.  
  16. using namespace std;
  17.  
  18. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  19.  
  20. #define PB push_back
  21. #define PII pair<int,int>
  22. #define PLL pair<ll,ll>
  23. #define MP make_pair
  24. #define fi first
  25. #define se second
  26.  
  27. #define SIZE(s) (int) (s).size()
  28.  
  29. #define INF 987654321
  30. #define ll long long
  31.  
  32. //----------------------
  33.  
  34. int N;
  35. int dlzka;
  36.  
  37. vector< pair<int, char> > V;
  38. vector< pair<int, char> > V2;
  39.  
  40. int find(double val)
  41. {
  42. 	FOR(i,0,SIZE(V2)-1)
  43. 		if (V2[i].fi >= val) return i;
  44. 	return -1;
  45. }
  46.  
  47. void solve2(int lavy, int pravy,int kolko)
  48. {
  49. 	int pozL = V2[lavy].fi;			
  50. 	int pozR = V2[pravy].fi;
  51. 	if (dlzka-pozR == pozL) printf("The last ant will fall down in %d seconds - started at %d and %d.\n",kolko,pozL,pozR);
  52. 	else if (dlzka-pozR > pozL) printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozR);
  53. 	else printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozL);
  54. }
  55.  
  56. void solve1(int lavy, int pravy,int kolko)
  57. {
  58. 	if (lavy == -1)
  59. 	{
  60. 		int pozR = V[pravy].fi;
  61. 		printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozR);
  62. 	}
  63. 	else  if (pravy == -1)
  64. 	{
  65. 		int pozL = V[lavy].fi;
  66. 		printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozL);
  67. 	}
  68. 	else
  69. 	{
  70. 		int pozL = V[lavy].fi;			
  71. 		int pozR = V[pravy].fi;
  72. 		if (dlzka-pozR == pozL) printf("The last ant will fall down in %d seconds - started at %d and %d.\n",kolko,pozL,pozR);
  73. 		else if (dlzka-pozR > pozL) printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozR);
  74. 		else printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozL);
  75. 	}
  76. }
  77.  
  78. int main()
  79. {
  80. 	char z;
  81. 	int poz;
  82.  
  83. 	while(scanf("%d %d",&dlzka,&N)==2)
  84. 	{
  85. 		V.clear();
  86. 		V2.clear();
  87.  
  88. 		int kolko=-1;
  89. 		int lavy = -1;
  90. 		int pravy = -1;
  91. 				bool existuje = false;
  92.  
  93. 		FOR(i,0,N-1)
  94. 		{
  95. 			scanf("%d %c",&poz,&z);
  96. 			//cout << poz << " " << z << endl;
  97. 			if (z == 'L') kolko = max(poz,kolko);
  98. 			else kolko = max(kolko,dlzka-poz);
  99. 			V.PB(MP(poz,z));
  100.  
  101. 		}
  102.  
  103. 		sort(V.begin(),V.end());
  104.  
  105. 		FOR(i,0,N-1)
  106. 		{
  107. 				if (i>0 && V[i-1].se == 'L' && V[i].se == 'R') existuje = true;
  108. 			if (V[i].se == 'L') lavy = i;
  109. 			if (pravy == -1 && V[i].se == 'R') pravy = i;
  110. 		}
  111.  
  112. 	//	cout << lavy << endl;
  113. 		FOR(i,0,N-1)
  114. 		{
  115. 			if (pravy == -1 && V[i].se == 'L')
  116. 			{
  117.  
  118. 			}
  119. 			else
  120. 				V2.PB(V[i]);
  121. 			if (lavy > 0 && lavy == i) break;
  122. 		}
  123.  
  124. 		if (existuje)
  125. 		{
  126. 			int pozL = V2[0].fi;			
  127. 			int pozR = V2[SIZE(V2)-1].fi;
  128. 		//	cout << pozL << " " << pozR << endl;
  129. 			double stred = (pozL+pozR) / 2.0;
  130. 			int idx1 = find(stred);
  131. 		//	cout << stred << " " << idx1 << endl;
  132.  
  133. 			int idx2 = idx1-1;
  134. 			solve2(idx2,idx1,kolko);
  135. 		}
  136. 		else
  137. 		{
  138. 			solve1(lavy,pravy,kolko);
  139. 		}
  140. 	}
  141.  
  142. 	return 0;
  143. }
  144.  
  145.