Advertisement
Guest User

Untitled

a guest
Apr 1st, 2020
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.97 KB | None | 0 0
  1. #pragma GCC optimize ("O3")
  2. #pragma GCC target ("sse4")
  3.  
  4. #include <bits/stdc++.h>
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7.  
  8. using namespace std;
  9. template <class T>
  10. using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
  11. template <class T>
  12. using ordered_multiset = __gnu_pbds::tree<T, __gnu_pbds::null_type, less_equal<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
  13.  
  14. #define PI atan2(0, -1)
  15. #define EPS 1e-9
  16. #define INF 5e18
  17. #define MOD 1000000007
  18.  
  19. #define mp make_pair
  20. #define pb push_back
  21. #define f first
  22. #define s second
  23. #define lb lower_bound
  24. #define ub upper_bound
  25.  
  26. int kase, N, arr [4][1010];
  27.  
  28. vector<long long> leastRotation(vector<long long> ori){
  29. vector<long long> S(2*(int)(ori.size())), f(2*(int)(ori.size()), -1);
  30. for(int i = 0; i < 2*(int)(ori.size()); i++) S[i] = ori[i%(int)ori.size()];
  31. int k = 0;
  32. for(int j = 1; j < S.size(); j++){
  33. int sj = S[j];
  34. int i = f[j - k - 1];
  35. while(i != -1 and sj != S[k + i + 1]){
  36. if(sj < S[k + i + 1])
  37. k = j - i - 1;
  38. i = f[i];
  39. }
  40. if(sj != S[k + i + 1]){
  41. if(sj < S[k])
  42. k = j;
  43. f[j - k] = -1;
  44. }
  45. else f[j - k] = i + 1;
  46. }
  47. vector<long long> ret((int)ori.size());
  48. for(int i = 0; i < ori.size(); i++) ret[i] = ori[(i+k)%(int)ori.size()];
  49. return ret;
  50. }
  51.  
  52. int main(){
  53. //freopen("sort.in", "r", stdin); freopen("sort.out", "w", stdout);
  54. ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10);
  55. cin >> kase;
  56. for(int kk = 1; kk <= kase; kk++){
  57. cin >> N;
  58. long long sum = 0;
  59. cout << "Case " << kk << ": ";
  60. for(int i = 0; i < 4; i++) for(int j = 0; j < N; j++){ cin >> arr[i][j]; sum += arr[i][j]; }
  61. if(sum%N){
  62. cout << "No\n";
  63. continue;
  64. }
  65. bool found = false;
  66. map<vector<long long>, int> freq;
  67. for(int i = 0; i < 4; i += 2)
  68. for(int shift = 0; shift < N && !found; shift++){
  69. vector<long long> temp;
  70. //cout << i << ' ' << shift << ' ';
  71. for(int j = 0; j < N; j++){
  72. if(i) temp.pb(arr[i][j]+arr[i+1][(j+shift)%N]);
  73. else temp.pb(sum/N-(arr[i][j]+arr[i+1][(j+shift)%N]));
  74. //cout << temp[j] << ' ';
  75. }
  76. //cout << endl;
  77. temp = leastRotation(temp);
  78. if(i == 0) freq[temp]++;
  79. else if(freq.find(temp) != freq.end()) found = true;
  80. }
  81. if(found) cout << "Yes\n";
  82. else cout << "No\n";
  83. }
  84. return 0;
  85. }
  86.  
  87. /******************************
  88. Kateba ii dake no hanashi darou
  89. Success is only a victory away
  90. - No Game No Life Opening
  91. ******************************/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement