fork(1) download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include<bits/stdc++.h>
  3. #include<unordered_map>
  4. using namespace std;
  5. typedef	long long ll;
  6. typedef unsigned long long ull;
  7. #define all(v) ((v).begin()),((v).end())
  8. #define sz(v) ((int)((v).size()))
  9. #define PI(n) ((double)acos(n))
  10. #define pw2(n) (1LL<<(n))
  11. #define sfi1(v) scanf("%d",&v)
  12. #define sfi2(v1,v2) scanf("%d%d",&v1,&v2)
  13. #define sfi3(v1,v2,v3) scanf("%d %d %d",&v1,&v2,&v3)
  14. int dx8[8] = { 1, -1, 0, 0, 1, 1, -1, -1 };
  15. int dy8[8] = { 0, 0, 1, -1, 1, -1, 1, -1 };
  16. void file()
  17. {
  18. #ifndef ONLINE_JUDGE
  19. 	freopen("in.txt", "r", stdin);
  20. 	//freopen("out.txt", "w", stdout);
  21. #else
  22. 	// online submission
  23. #endif
  24. }
  25. void fast()
  26. {
  27. 	std::ios_base::sync_with_stdio(0);
  28. 	cin.tie(NULL); cout.tie(NULL);
  29. }
  30. #define pair1 pair<int,int> 
  31. int n;
  32.  
  33.  
  34. int dp[100001][2];
  35. int v[100001];
  36. int vis[100000];
  37. //  0 >> i+d    1 >> i-d  
  38. int calc(int node){
  39. 	if (node == n)
  40. 		return 0;
  41. 	if (node > n || (node <= 0))
  42. 		return 1e9;
  43.  
  44. 	if (dp[node][0] != -1 && dp[node][1] != -1){
  45. 		return min(dp[node][0], dp[node][1]);
  46. 	}
  47. 	int mn = 1e9;
  48. 	if (dp[node][0] == -1){
  49. 		dp[node][0] = 1e9;
  50. 		mn = min(mn, calc(node + v[node]) + 1);
  51. 	}
  52. 	if (dp[node][1] == -1){
  53. 		dp[node][1] = mn;
  54. 		mn = min(mn, calc(node - v[node]) + 1);
  55. 	}
  56. 	if (dp[node][1] != -1 && dp[node][0] != -1){
  57. 		// min between  i-d  , i+d 
  58. 		mn = min(dp[node][1], mn);
  59. 		mn = min(dp[node][0], mn);
  60. 		dp[node][0] = dp[node][1] = mn;
  61. 	}
  62. 	return  mn;
  63. }
  64. int main()
  65. {
  66. 	file();
  67. 	//freopen("jumping.in", "r", stdin);
  68. 	int t;
  69. 	cin >> t;
  70. 	while (t--){
  71. 		sfi1(n);
  72. 		for (int i = 1; i <= n; i++){
  73. 			int a;
  74. 			sfi1(a);
  75. 			v[i] = a;
  76. 		}
  77. 		memset(dp, -1, sizeof dp);
  78. 		vector<int>ans(n + 1);
  79. 		for (int i = 1; i <= n; i++){
  80. 			ans[i] = calc(i);
  81. 		}
  82. 		for (int i = 1; i <= n; i++){
  83. 			if (ans[i] == 1e9) ans[i] = -1;
  84. 			printf("%d\n", ans[i]);
  85. 		}
  86. 	}
  87. }
Time limit exceeded #stdin #stdout 5s 5024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aqsOkm
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!