fork download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<algorithm>
  5. using namespace std;
  6. int main()
  7. {
  8. 	int t;
  9. 	scanf("%d",&t);
  10. 	typedef long long int LI;
  11. 	LI n,a[100005];
  12. 	bool buffer[100005];
  13. 	LI left,right,cnt;
  14. 	char x[100005];
  15. 	while(t--){
  16. 		cnt=0;
  17. 		fill(buffer,buffer+100005,false);
  18. 		scanf("%lld",&n);
  19. 	for(int i=1;i<=n;i++)
  20. 	{
  21. 		scanf("%s%lld",x,&a[i]);
  22. 		if(!buffer[a[i]]&&a[i]>0&&a[i]<=n)
  23. 		{
  24. 		buffer[a[i]]=true;
  25. 		a[i]=-1;
  26. 		}
  27. 	}
  28. LI c1=-1,c2=-1;
  29. 	for(int i=1;i<=n;i++)
  30. 	{
  31. 		if(a[i]!=-1&&a[i]>=1&&a[i]<=n)
  32. 		{
  33. 			LI left,right;
  34. 			left=a[i];
  35. 			right=a[i];
  36. 			//printf("L=%lld\n",left);
  37. 			while(true)
  38. 			{
  39. 				if(left==0)
  40. 				{
  41. 					break;
  42. 				}
  43. 				if(!buffer[left])
  44. 				{
  45. 				c1=(a[i]-left);
  46. 				break;
  47. 				}
  48. 				left--;
  49. 			}
  50. 			while(true)
  51. 			{
  52. 				if(right==n+1)
  53. 				{
  54. 					break;
  55. 				}
  56. 				if(!buffer[right])
  57. 				{
  58. 					c2=(right-a[i]);
  59. 					//printf("%lld",right);
  60. 					break;
  61. 				}
  62. 				right++;
  63. 			}
  64.  
  65.  
  66. 	if(c1!=-1)
  67. 	{
  68. 		if(c2==-1)
  69. 		{
  70. 			buffer[left]=true;
  71. 			cnt+=c1;
  72. 		}
  73. 		else if(c2!=-1)
  74. 		{
  75. 			if(c1<c2)
  76. 			{
  77. 				buffer[left]=true;
  78. 				cnt+=c1;
  79. 			}
  80. 			else
  81. 			{
  82. 				buffer[right]=true;
  83. 				cnt+=c2;
  84. 			}
  85. 		}
  86. 	}
  87. 	else if(c1==-1)
  88. 	{
  89. 		//printf("in");
  90. 		if(c2!=-1)
  91. 		{
  92. 			buffer[right]=true;
  93. 			cnt+=c2;
  94. 		}
  95. 		else
  96. 		{
  97. 			while(left>0&&left<=n&&!buffer[left])
  98. 			left++;
  99. 			if(left>0&&left<=n)
  100. 			{
  101. 				c1=a[i]-left;
  102. 			}
  103. 			while(right>0&&right<=n&&!buffer[right])
  104. 			right--;
  105. 			if(right>0&&right<=n)
  106. 			c2=right-a[i];
  107.  
  108. 		}
  109.  
  110. 	}
  111. 	}
  112. 	else if(a[i]!=-1)
  113. 	{
  114. 		LI t1=a[i],t2=a[i];
  115. 		LI cnt1=0;
  116. 		int f=-1;
  117. 		if(t1<=0)
  118. 		{
  119. 			while(t1<=0)
  120. 			{
  121. 				t1++;
  122. 				cnt++;
  123. 			}
  124. 			while(buffer[t1])
  125. 			{
  126. 			t1++;
  127. 			cnt1++;
  128. 			}
  129. 			if(t1<=n)
  130. 			{
  131. 			f=1;
  132. 			buffer[t1]=true;
  133. 			}
  134. 		}
  135. 		else
  136. 		{
  137. 			cnt1=0;
  138. 			while(t2>n)
  139. 			{
  140. 				t2--;
  141. 				cnt1++;
  142. 			}
  143. 			while(buffer[t2])
  144. 			{
  145. 			t2--;
  146. 			cnt1++;
  147. 			}
  148. 			if(t2>0&&t2<=n)
  149. 			{
  150. 			f=2;
  151. 			buffer[t2]=true;
  152. 			}
  153. 		}
  154. 		if(f==1)
  155. 		{
  156. 		cnt+=cnt1;
  157. 		continue;
  158. 		}
  159. 		else
  160. 		{
  161. 			cnt+=cnt1;
  162. 			continue;
  163. 		}
  164.  
  165. 	}
  166. 	}
  167. 	printf("%lld\n",cnt);
  168. 	}
  169.  
  170. 	return 0;
  171. }
Success #stdin #stdout 0s 4312KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/O4ood1
language:
C++ (gcc 8.3)
created:
9 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!