CSU 1581Clock Pictures Hash

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <vector> #include <algorithm> template <class T> inline bool rd(T &ret) { char c; int sgn; if (c = getchar(),c == EOF) return 0; while (c != '-' && (c<'0' || c>'9')) c = getchar(); sgn = (c == '-') ? ⑴ : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(),c >= '0'&&c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if (x>9) pt(x / 10); putchar(x % 10 + '0'); } using namespace std; const int N = 200105; typedef long long ll; const int MAGIC = 311,MOD = 1e9 + 7; template <class T> struct HASH{ ll h[N],base[N]; inline void init(T *s,int len) { h[0] = 1; for (int i = 1; i <= len; ++i) h[i] = (h[i - 1] * MAGIC % MOD + s[i - 1]) % MOD; base[0] = 1; for (int i = 1; i <= len; ++i) base[i] = (base[i - 1] * MAGIC) % MOD; } inline long long get(int l,int r) { return (h[r] - h[l - 1] * base[r - l + 1] % MOD + MOD) % MOD; } }; HASH <int>A,B; int a[N],b[N],n; ll x[N],y[N]; int main(){ while (~scanf("%d",&n)){ for (int i = 0; i < n; i++)rd(a[i]); for (int i = 0; i < n; i++)rd(b[i]); sort(a,a + n); sort(b,b + n); a[n] = a[0]; b[n] = b[0]; for (int i = 0; i < n; i++){ a[i] = a[i + 1] - a[i]; if (a[i] < 0) a[i] += 360000; b[i] = b[i + 1] - b[i]; if (b[i] < 0) b[i] += 360000; } // for(int i = 0;i < n; i++)cout<<a[i]<<" "; puts(""); // for(int i = 0;i < n; i++)cout<<b[i]<<" "; puts(""); A.init(a,n); B.init(b,n); bool ok = A.get(1,n) == B.get(1,n); for (int i = 2; i <= n && ok == false; i++){ int len = n - i; // printf("(%d,%d)-(%d,%d) ",1,len+1,i,n); // printf("(%d,len+2,n,i⑴); if (A.get(1,len + 1) == B.get(i,n) && A.get(len + 2,i - 1)) ok = true; } if (ok)puts("possible"); else puts("impossible"); } return 0; }