fork(3) download
copy 
  1. // Cleaning Robot (F), by Errichto
  2. // AC, O(w+h+n)
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. #define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
  6. #define RI(i,n) FOR(i,1,(n))
  7. #define REP(i,n) FOR(i,0,(n)-1)
  8. typedef long long ll;
  9.  
  10. const int nax = 5e5 + 5;
  11. const int mod = 1e9 + 7;
  12. char sl[nax];
  13.  
  14. int n;
  15. int ans;
  16. int low[2], high[2], curr[2], dimension[2];
  17.  
  18. bool f(ll moves, bool cheating) {
  19. 	if(moves != 0 && moves % n == 0 && curr[0] == 0 && curr[1] == 0) {
  20. 		puts("-1");
  21. 		exit(0);
  22. 	}
  23. 	char type = sl[moves%n];
  24. 	if(type == 'L') cheating ? curr[0] = high[0]+1 : ++curr[0];
  25. 	else if(type == 'R') cheating ? curr[0] = low[0]-1 : --curr[0];
  26. 	else if(type == 'U') cheating ? curr[1] = high[1]+1 : ++curr[1];
  27. 	else if(type == 'D') cheating ? curr[1] = low[1]-1 : --curr[1];
  28. 	else assert(false);
  29. 	bool something_happened = false;
  30. 	REP(i, 2) {
  31. 		if(curr[i] < low[i] || curr[i] > high[i]) {
  32. 			ans = (ans + (moves + 1) % mod * dimension[i^1]) % mod;
  33. 			--dimension[i];
  34. 			something_happened = true;
  35. 		}
  36. 		if(curr[i] < low[i]) low[i] = curr[i];
  37. 		if(curr[i] > high[i]) high[i] = curr[i];
  38. 	}
  39. 	return something_happened;
  40. }
  41.  
  42. bool inGame() { return dimension[0] > 0 && dimension[1] > 0; }
  43.  
  44. int main() {
  45. 	scanf("%d%d%d", &n, &dimension[1], &dimension[0]);
  46. 	scanf("%s", sl);
  47.  
  48. 	for(ll moves = 0; inGame() && moves < n; ++moves)
  49. 		f(moves, false);
  50. 	vector<int> w;
  51. 	for(ll moves = n; inGame() && moves < 2 * n; ++moves)
  52. 		if(f(moves, false)) w.push_back((int) moves % n);
  53.  
  54.  
  55. 	for(ll k = 2; inGame(); ++k)
  56. 		for(int moves : w) if(inGame())
  57. 			f(k*n + moves, true);
  58. 	printf("%d\n", ans);
  59. 	return 0;
  60. }
Success #stdin #stdout 0s 3952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/xrU9u2
Robot
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!