fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <list>
  7. #include <ctime>
  8. #include <cstdio>
  9. #include <stack>
  10. #include <cstring>
  11. #include <climits>
  12. #include <cmath>
  13. #include <string>
  14. #include <functional>
  15. #include <sstream>
  16. #include <map>
  17. #include <set>
  18.  
  19. #pragma comment(linker, "/STACK:100000000000000")
  20.  
  21. using namespace std;
  22. #define     For(i,a,b)        for (int i=a; i<b; i++)
  23. #define     Rep(i,a)          for (int i=0; i<a; i++)
  24. #define     ALL(v)            (v).begin(),(v).end()
  25. #define     Set(a,x)          memset((a),(x),sizeof(a))
  26. #define     EXIST(a,b)        find(ALL(a),(b))!=(a).end()
  27. #define     Sort(x)           sort(ALL(x))
  28. #define     UNIQUE(v)         Sort(v); (v).resize(unique(ALL(v)) - (v).begin())
  29. #define     MP                make_pair
  30. #define     SF                scanf
  31. #define     PF                printf
  32. #define     MAXN              1001
  33. #define     MOD               1000000007
  34. #define     Dbug              cout<<"";
  35. #define     EPS               1e-8
  36. #define     timestamp(x)      printf("Time : %.3lf s.\n", clock()*1.0/CLOCKS_PER_SEC)
  37. typedef long long ll;
  38. typedef pair<int,int> pii;
  39. int n, arr[4][MAXN];
  40. ll h[MAXN][MAXN][2], goal[MAXN], h2[MAXN], pw[MAXN];
  41. ll x=1234567891, tmp[MAXN];
  42. int main(){
  43. 	//ios_base::sync_with_stdio(false);
  44. 	//freopen("a.in","r",stdin);
  45. 	int tc, cas=1;
  46. 	SF("%d", &tc);
  47. 	pw[0]=1;
  48. 	For(i, 1, MAXN) pw[i]=pw[i-1]*x;
  49. 	while (tc--)
  50. 	{
  51. 		SF("%d", &n);
  52. 		ll sum=0;
  53. 		Rep(i, 4) Rep(j, n)
  54. 		{
  55. 			SF("%d", &arr[i][j]);
  56. 			sum+=arr[i][j];
  57. 		}
  58. 		if(sum%n)
  59. 		{
  60. 			PF("Case %d: No\n", cas++);
  61. 			continue;
  62. 		}
  63. 		sum/=n;
  64. 		bool pr=0;
  65. 		Rep(i, n) 
  66. 		{
  67. 			goal[i]=sum-arr[0][i];
  68. 			if(goal[i]<0)
  69. 			{
  70. 				PF("Case %d: No\n", cas++);
  71. 				pr=1;
  72. 				break;
  73. 			}
  74. 		}
  75. 		if(pr) continue;
  76. 		Rep(i, n) 
  77. 		{
  78. 			h2[i]=0;
  79. 			Rep(j, n) 
  80. 			{
  81. 				ll t=goal[j]-arr[3][(i+j)%n];
  82. 				h2[i]*=x;
  83. 				h2[i]+=t;
  84. 			}
  85. 		}
  86. 		sort(h2, h2+n);
  87. 		Rep(i, n)
  88. 		{
  89. 			Rep(j, n)
  90. 			{
  91. 				ll t=arr[1][j]+arr[2][(i+j)%n];
  92. 				tmp[j]=t;
  93. 				if(j) h[i][j][0]=h[i][j-1][0]*x+t;
  94. 				else h[i][j][0]=t;
  95. 			}
  96. 			for(int j=n-1; j>=0; j--)
  97. 				h[i][j][1]=pw[n-j-1]*tmp[j]+h[i][j+1][1];
  98. 		}
  99. 		Rep(i, n) Rep(j, n)
  100. 		{
  101. 			ll a=0, b;
  102. 			if(j) a=h[i][j-1][0];
  103. 			b=h[i][j][1];
  104. 			ll t=b*pw[j]+a;
  105.  			if(binary_search(h2, h2+n, t)) 
  106. 			{
  107. 				PF("Case %d: Yes\n", cas++);
  108. 				pr=1;
  109. 				i=n;
  110. 				break;
  111. 			}
  112. 		}
  113. 		if(pr) continue;
  114. 		PF("Case %d: No\n", cas++);
  115. 	}
  116. 	return 0;
  117. }
Runtime error #stdin #stdout 0s 19048KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/edfe7Q
language:
C++14 (gcc 8.3)
created:
10 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!