fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <list>
  4. #include <vector>
  5.  
  6. #define FOR(i,a,b) for(int i = (a); i <= (b); i++)
  7. #define FR(i,a) for(int i = 0; i < (a); i++)
  8. using namespace std;
  9.  
  10.  
  11. long T,N, s[],d[],w[];
  12.  
  13. long nextstart_idx,nextdeadline_idx;
  14. struct item
  15. {
  16. 	double start,end,w;
  17. };
  18. struct copitem
  19. {
  20. 	double start,end,a_idx;
  21. };
  22. struct sort_by_one_item
  23. {
  24. 	bool operator () (const item &lhs , const item& rhs) // replace YourStruct
  25. 	{
  26. 		if(lhs.end == rhs.end)
  27. 			return lhs.start < rhs.start;
  28.  
  29. 		return lhs.end < rhs.end;
  30. 	}
  31. };
  32. struct sort_by_one_copitem
  33. {
  34. 	bool operator () (const copitem &lhs , const copitem& rhs) // replace YourStruct
  35. 	{
  36. 		if(lhs.start == rhs.start)
  37. 			return lhs.end < rhs.end;
  38.  
  39. 		return lhs.start < rhs.start;
  40. 	}
  41. };
  42. vector<item> a,savea;
  43. vector<copitem> b,saveb;
  44.  
  45. bool check(long speed)
  46. {
  47. 	long count=0;
  48. 	while (count<a.size())
  49. 	{
  50. 		long i=0;
  51. 		while (!b[i].start)
  52. 		{
  53. 			i++;
  54. 		}
  55. 		nextstart_idx = b[i].a_idx;
  56. 		nextdeadline_idx = 0; 		
  57. 		while (!a[nextdeadline_idx].start)
  58. 		{
  59. 			nextdeadline_idx++;
  60. 		}
  61. 		if (a[nextstart_idx].start==a[nextdeadline_idx].start && (nextstart_idx!=nextdeadline_idx) )
  62. 		{
  63. 				nextstart_idx = nextdeadline_idx;
  64. 				i=0;
  65. 				while (b[i].a_idx!=nextstart_idx) i++;
  66. 		}
  67. 		if (nextdeadline_idx==nextstart_idx)
  68. 		{
  69. 			if (nextdeadline_idx<a.size()-1)
  70. 				if (a[nextdeadline_idx+1].end==a[nextdeadline_idx].end) return false;
  71. 			if ((double)a[nextstart_idx].w/(double)speed + (double)(a[nextstart_idx].start) > (double)(a[nextstart_idx].end)) return false;
  72. 			// do all job, clear b[0] and a[0]
  73. 			//a.erase(a.begin());b.erase(b.begin());
  74.  
  75.  
  76. 			if (i<b.size()-1)
  77. 			{
  78. 				long j=-1,min=100000;
  79. 				FR(v,b.size()-1)
  80. 				{
  81. 					if (b[v].start<min && v!=i && b[v].start) {j=v;min=b[v].start;}
  82. 				}	
  83. 				if (j>-1)
  84. 				if (b[j].start <= (double)a[nextstart_idx].w/(double)speed + (double)(a[nextstart_idx].start))
  85. 					{
  86. 						b[j].start = (double)a[nextstart_idx].w/(double)speed + (double)(a[nextstart_idx].start);
  87. 						a[b[j].a_idx].start = (double)a[nextstart_idx].w/(double)speed + (double)(a[nextstart_idx].start);
  88. 					}
  89. 			}
  90. 			a[nextstart_idx].end=0; a[nextstart_idx].start = 0;
  91. 			b[i].end=0; b[i].start=0;			
  92. 			count++;
  93. 			// check false case
  94.  
  95. 			continue;
  96. 		}
  97. 		if (a[nextstart_idx].end > a[nextdeadline_idx].start)
  98. 		{
  99. 			a[nextstart_idx].w -= speed*(a[nextdeadline_idx].start - a[nextstart_idx].start);
  100. 			if (a[nextstart_idx].w <=0) 
  101. 			{
  102. 				a[nextstart_idx].end=0; a[nextstart_idx].start = 0;
  103. 				b[nextdeadline_idx].end=0; b[nextdeadline_idx].start=0;
  104. 				count++;
  105. 				continue;
  106. 			}
  107. 			a[nextstart_idx].start = a[nextdeadline_idx].start;
  108. 			b[i].start = a[nextdeadline_idx].start;
  109. 		}
  110. 	}
  111. 	return true;
  112.  
  113. }
  114. long long find(long left, long right)
  115. {
  116. 	b=saveb;a=savea;
  117. 	if (left==right-1)
  118. 	{
  119. 			if (check(left)) return left;
  120. 			else return right;
  121. 	}
  122. 	long mid = (left+right)/2;
  123. 	if (check(mid)) return find(left,mid);
  124. 	else return find(mid,right);	
  125. }
  126.  
  127.  
  128. void process()
  129. {
  130. 	sort(a.begin(),a.end(),sort_by_one_item());
  131. 	b.clear();
  132. 	FR(v,N)
  133. 	{
  134. 		item temp = a[v];
  135. 		copitem temp1;
  136. 		temp1.end = temp.end; temp1.start = temp.start; temp1.a_idx = v;
  137. 		b.push_back(temp1);
  138. 	}
  139. 	sort(b.begin(),b.end(),sort_by_one_copitem());
  140. 	savea=a;saveb=b;
  141. 	long long t = find(0,10000);
  142. 	printf("%d\n",t);
  143. }
  144. int main ()
  145. {
  146. 	scanf("%d", &T);
  147. 	FR(o,T)
  148. 	{
  149. 		a.clear();
  150. 		scanf("%d", &N);
  151. 		FR(v,N)
  152. 		{
  153. 			item temp;
  154. 			scanf("%lf%lf%lf", &temp.start,&temp.end,&temp.w);
  155. 			a.push_back(temp);		
  156. 		}
  157. 		process();
  158. 	}
  159. 	return 0;
  160. }
  161.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
1
8
15 18 10 
20 24 16 
8 15 33 
11 14 14 
1 6 16 
16 19 12 
3 5 12 
22 25 10
compilation info 
prog.cpp:11: error: storage size of ‘s’ isn't known
prog.cpp:11: error: storage size of ‘d’ isn't known
prog.cpp:11: error: storage size of ‘w’ isn't known
prog.cpp: In function ‘bool check(long int)’:
prog.cpp:48: warning: comparison between signed and unsigned integer expressions
prog.cpp:69: warning: comparison between signed and unsigned integer expressions
prog.cpp:76: warning: comparison between signed and unsigned integer expressions
prog.cpp:79: warning: comparison between signed and unsigned integer expressions
prog.cpp: In function ‘void process()’:
prog.cpp:142: warning: format ‘%d’ expects type ‘int’, but argument 2 has type ‘long long int’
prog.cpp: In function ‘int main()’:
prog.cpp:146: warning: format ‘%d’ expects type ‘int*’, but argument 2 has type ‘long int*’
prog.cpp:150: warning: format ‘%d’ expects type ‘int*’, but argument 2 has type ‘long int*’
prog.cpp:146: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:150: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:154: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
stdout
copy 
Standard output is empty
https://ideone.com/CmahL
language:
C++ (gcc 8.3)
created:
14 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!