fork(1) download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <queue>
  5. #include <stack>
  6. #include <algorithm>
  7. #include <cstdio>
  8.  
  9. using namespace std;
  10.  
  11. long long int c[200001],b[200001], d[200001], e[200001];
  12. int n;
  13.  
  14. long long int mod(long long int p) {
  15. 	if(p==n) {
  16. 		return 0;
  17. 	}
  18. 	return p;
  19. }
  20.  
  21. int main() {
  22. 	ios::sync_with_stdio(false);
  23. 	cin>>n;
  24. 	long long int a[n];
  25. 	for(int i = 0; i < n; i++) {
  26. 		cin>>a[i];
  27. 	}
  28. 	long long int x,y,ans,t;
  29. 	long long int sum1 = 0;
  30. 	for(int i =0; i < n; i++) {
  31. 		sum1 += a[i];
  32. 	}
  33. 	cin>>x>>y;
  34. 	int cur = 0;
  35. 	long long int p = 0, sum =0;
  36. 	t = x%sum1;
  37. 	long long int dd = x/sum1;
  38. 	while(sum <= t) {
  39. 		sum += a[p];
  40. 		p++;
  41. 		p = mod(p);
  42. 	}
  43. 	for(int i = 0; i < n; i++) {
  44. 		d[i] = (p-1+n)%n;
  45. 		//cout<<d[i]<<endl;
  46. 		e[i] = (sum-a[d[i]]) + (dd*sum1);
  47. 		//cout<<e[i]<<endl;
  48. 		sum -= a[i];
  49. 		while(sum <= t) {
  50. 			sum += a[p];
  51. 			p++;
  52. 			p = mod(p);
  53. 		}
  54.  
  55. 	}
  56. 	long long int day = 0, dist = 0;
  57. 	while(b[cur]==0) {
  58. 		b[cur] = day;
  59. 		c[cur] = dist;
  60. 		long long int t = x;
  61. 		if(x < a[cur]) {
  62. 			cout<<-1<<endl;
  63. 			return 0;
  64. 		}
  65. 		long long int dist_move = e[cur];
  66. 		cur = d[cur];
  67. 		y -= dist_move;
  68. 		dist += dist_move;
  69. 		//cout<<cur<<" "<<dist<<endl;
  70. 		day++;
  71. 		if(y <= 0) {
  72. 			//cerr<<231<<endl;
  73. 			cout<<day<<endl;
  74. 			return 0;
  75. 		}
  76. 	}
  77. 	long long int dist_period = dist -c[cur];
  78. 	day += (y / dist_period)*(day - b[cur]);
  79. 	y %= dist_period;
  80. 	//cout<<y<<endl;
  81. 	while(y > 0) {
  82. 		long long int t = x;
  83. 		long long int dist_move = e[cur];
  84. 		cur = d[cur];
  85. 		y -= dist_move;
  86. 		day++;
  87. 		if(y<0) {
  88. 			cout<<day<<endl;
  89. 			return 0;
  90. 		}
  91. 	}
  92. 	cout<<day<<endl;
  93.  
  94. }
Runtime error #stdin #stdout 0s 9712KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cysMiz
language:
C++14 (gcc 8.3)
created:
7 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!