fork download
copy 
  1. #include<iostream>
  2. #include<climits>
  3. using namespace std;
  4.  
  5. int n;
  6. int a[5000],d[50010];
  7. bool visit[50010];
  8. int heap[50010],hp=-1,arrtoheap[50010];
  9.  
  10. void swap(int i,int j)
  11. {
  12. 	int t;
  13.  
  14. 	t = arrtoheap[heap[i]];
  15. 	arrtoheap[heap[i]] = arrtoheap[heap[j]];
  16. 	arrtoheap[heap[j]] = t;
  17.  
  18. 	t = heap[i];
  19. 	heap[i] = heap[j];
  20. 	heap[j] = t; 	
  21. }
  22.  
  23. void insert(int a)
  24. {
  25. 	heap[++hp] = a;
  26. 	arrtoheap[a] = hp;
  27. 	int i=hp;
  28.  
  29. 	while((i-1)>=0)
  30. 	{
  31. 		if(d[heap[(i-1)/2]]>d[heap[i]])
  32. 			swap(i,(i-1)/2);
  33. 		else
  34. 			break;
  35.  
  36. 		i = (i-1)/2;
  37. 	}
  38. }
  39.  
  40. void heapify(int i)
  41. {
  42. 	int j,minn;
  43. 	int l = 2*i+1 , r = 2*i+2;
  44. 	minn = i;
  45.  
  46. 	if((l<=hp) && (d[heap[l]]<d[heap[minn]]))
  47. 		minn = l;
  48.  
  49. 	if((r<=hp) && (d[heap[r]]<d[heap[minn]]))
  50. 		minn = r;
  51.  
  52. 	if(minn!=i)
  53. 	{
  54. 		swap(minn,i);
  55. 		heapify(minn);	
  56. 	}
  57. }
  58.  
  59. void update(int i,int val)
  60. {
  61. 	int j,minn=INT_MAX;
  62. 	d[heap[i]] = val;
  63.  
  64. 	if( (2*i+1) <= hp )
  65. 		minn = d[heap[2*i+1]];
  66. 	if( (2*i+2) <= hp )
  67. 		minn = min(minn,d[heap[2*i+2]]);
  68.  
  69. 	if(d[heap[i]]>minn)
  70. 		heapify(i);	
  71. 	else
  72. 	{
  73. 		while((i-1)>=0)
  74. 		{
  75. 			if(d[heap[(i-1)/2]]>d[heap[i]])
  76. 				swap(i,(i-1)/2);
  77. 			else
  78. 				break;
  79.  
  80. 			i = (i-1)/2;
  81. 		}
  82. 	}
  83. }
  84.  
  85. void dikstra()
  86. {
  87. 	insert(0);
  88. 	int an,i,j;
  89.  
  90. 	while(hp!=-1)
  91. 	{
  92. //		for(i=0;i<=hp;++i)
  93. //			cout<<heap[i]<<' ';
  94. //		cout<<'\n';
  95.  
  96. 		an = heap[0];	
  97. 		swap(0,hp);
  98. 		arrtoheap[heap[hp]]=-1;
  99. 		--hp;
  100. 		heapify(0);
  101.  
  102. 		if(visit[an] == true)
  103. 			continue;
  104. 		visit[an] = true;
  105.  
  106. 		for(i=1;i<n;++i)
  107. 		{
  108. 			j = (a[i]+an)%a[0];
  109.  
  110. 			if(a[i]+d[an]<d[j])	
  111. 			{
  112. 				if(arrtoheap[j]!=-1)
  113. 					update(arrtoheap[j],a[i]+d[an]);
  114. 				else
  115. 				{
  116. 					d[j] = a[i]+d[an];
  117. //					if(visit[j]!=true)
  118. 						insert(j);
  119. 				}
  120. 			}
  121. 		}
  122. 	}
  123. }
  124.  
  125. int main()
  126. {
  127. 	int i,j;
  128.  
  129. 	cin>>n;
  130.  
  131. 	for(i=0;i<n;++i)
  132. 		cin>>a[i];
  133.  
  134. 	for(i=0;i<a[0];++i)
  135. 	{
  136. 		d[i] = INT_MAX;
  137. 		visit[i] = false;
  138. 		arrtoheap[i] = -1;
  139. 	}
  140. 	d[0] = 0;
  141.  
  142. 	dikstra();
  143.  
  144. //	for(i=0;i<a[0];++i)
  145. //		cout<<d[i]<<' ';
  146.  
  147. 	cin>>j;
  148.  
  149. 	while(j--)
  150. 	{
  151. 		cin>>i;
  152.  
  153. 		if(d[i%a[0]]<=i)
  154. 			cout<<"TAK\n";
  155. 		else
  156. 			cout<<"NIE\n";
  157. 	}
  158.  
  159. 	return 0;	
  160. }
Success #stdin #stdout 0s 16720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/D5rJ4f
Tasks Sums
language:
C++14 (gcc 8.3)
created:
6 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!