Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize ("O3")
- #pragma GCC target ("sse4")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- template <class T>
- 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>;
- template <class T>
- 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>;
- #define PI atan2(0, -1)
- #define EPS 1e-9
- #define INF 5e18
- #define MOD 1000000007
- #define mp make_pair
- #define pb push_back
- #define f first
- #define s second
- #define lb lower_bound
- #define ub upper_bound
- int kase, N, arr [4][1010];
- vector<long long> leastRotation(vector<long long> ori){
- vector<long long> S(2*(int)(ori.size())), f(2*(int)(ori.size()), -1);
- for(int i = 0; i < 2*(int)(ori.size()); i++) S[i] = ori[i%(int)ori.size()];
- int k = 0;
- for(int j = 1; j < S.size(); j++){
- int sj = S[j];
- int i = f[j - k - 1];
- while(i != -1 and sj != S[k + i + 1]){
- if(sj < S[k + i + 1])
- k = j - i - 1;
- i = f[i];
- }
- if(sj != S[k + i + 1]){
- if(sj < S[k])
- k = j;
- f[j - k] = -1;
- }
- else f[j - k] = i + 1;
- }
- vector<long long> ret((int)ori.size());
- for(int i = 0; i < ori.size(); i++) ret[i] = ori[(i+k)%(int)ori.size()];
- return ret;
- }
- int main(){
- //freopen("sort.in", "r", stdin); freopen("sort.out", "w", stdout);
- ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10);
- cin >> kase;
- for(int kk = 1; kk <= kase; kk++){
- cin >> N;
- long long sum = 0;
- cout << "Case " << kk << ": ";
- for(int i = 0; i < 4; i++) for(int j = 0; j < N; j++){ cin >> arr[i][j]; sum += arr[i][j]; }
- if(sum%N){
- cout << "No\n";
- continue;
- }
- bool found = false;
- map<vector<long long>, int> freq;
- for(int i = 0; i < 4; i += 2)
- for(int shift = 0; shift < N && !found; shift++){
- vector<long long> temp;
- //cout << i << ' ' << shift << ' ';
- for(int j = 0; j < N; j++){
- if(i) temp.pb(arr[i][j]+arr[i+1][(j+shift)%N]);
- else temp.pb(sum/N-(arr[i][j]+arr[i+1][(j+shift)%N]));
- //cout << temp[j] << ' ';
- }
- //cout << endl;
- temp = leastRotation(temp);
- if(i == 0) freq[temp]++;
- else if(freq.find(temp) != freq.end()) found = true;
- }
- if(found) cout << "Yes\n";
- else cout << "No\n";
- }
- return 0;
- }
- /******************************
- Kateba ii dake no hanashi darou
- Success is only a victory away
- - No Game No Life Opening
- ******************************/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement