#include #include #include #include #include using namespace std; typedef long long ll; /* * Author * Robin Lee (hex539) * * Algorithm * Generate a suffix array for the circular string using the power-of-two * method. Rotate to the lexicographically smallest element and compare * from there. * * Complexity * O(N log^2 N) */ void normalise(basic_string &s){ map renum; int cnt=0; for (int i=s.length(); i--;) renum[s[i]]; for (map::iterator it=renum.begin(); it!=renum.end(); ++it) it->second=cnt++; for (int i=s.length(); i--;) s[i]=renum[s[i]]; } int min_rotation(basic_string s){ normalise(s); for (int radius=1; radius<=(1<<22); radius<<=1){ basic_string t=s; for (int i=0; i read_clock(int n){ int const modulo = 360000; vector v(n); for (int i=0; i>v[i]; sort(v.begin(),v.end()); v.push_back(v.front()); basic_string s; for (int i=0; i>n; basic_string a=read_clock(n), b=read_clock(n); cout<<(a==b? "possible": "impossible")<