fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. typedef long long ll;
  4. typedef unsigned long long ull;
  5. #define endl '\n'
  6. #define fast                    \
  7.   ios_base::sync_with_stdio(0); \
  8.   cin.tie(0);
  9.  
  10. #define forn(i, n) for (int i = 0; i < n; i++)
  11. #define fornm(i, n, m) for (int i = n; i <= m; i++)
  12. #define rforn(in, n) for (int i = n - 1; i >= 0; i--)
  13.  
  14. #define all(x) x.begin(), x.end()
  15. #define len(x) int(x.size())
  16.  
  17. #define ms(x, n) memset(x, n, sizeof(x))
  18.  
  19. #define find(x, n) find(all(x), n) != x.end()
  20.  
  21. #define suma(a, b) ((a % MOD) + (b $ MOD)) % MOD
  22. #define resta(a, b) ((a % MOD) - (b $ MOD)) % MOD
  23.  
  24. //" \n"[i == n - 1]
  25. using namespace std;
  26.  
  27. class HashedString {
  28.   private:
  29. 	// change M and B if you want
  30. 	static const long long M = 1e9 + 9;
  31. 	static const long long B = 9973;
  32.  
  33. 	// pow[i] contains B^i % M
  34. 	static vector<long long> pow;
  35.  
  36. 	// p_hash[i] is the hash of the first i characters of the given string
  37. 	vector<long long> p_hash;
  38.  
  39.   public:
  40. 	HashedString(const string &s) : p_hash(s.size() + 1) {
  41. 		while (pow.size() < s.size()) { pow.push_back((pow.back() * B) % M); }
  42.  
  43. 		p_hash[0] = 0;
  44. 		for (int i = 0; i < s.size(); i++) {
  45. 			p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
  46. 		}
  47. 	}
  48.  
  49. 	long long get_hash(int start, int end) {
  50. 		long long raw_val =
  51. 		    (p_hash[end + 1] - (p_hash[start] * pow[end - start + 1]));
  52. 		return (raw_val % M + M) % M;
  53. 	}
  54. };
  55. vector<long long> HashedString::pow = {1};
  56.  
  57. void solve()
  58. {
  59.   int n; cin >> n;
  60.   string grid[n][n];
  61.   forn(i, n) {
  62.     forn (j, n) {
  63.       cin >> grid[i][j];
  64.     }
  65.   }
  66.  
  67.   if (n == 2) {
  68.     HashedString one(grid[0][1]);
  69.     HashedString two(grid[1][0]);
  70.     int oc = 0;
  71.     int idx = -1;
  72.     set< array<string, 2> > ans;
  73.     forn (i, len(grid[0][1])-1) {
  74.       if (
  75.         one.get_hash(0, i) == two.get_hash(len(grid[1][0])-i-1, len(grid[1][0])-1) &&
  76.         one.get_hash(i+1, len(grid[0][1])-1) == two.get_hash(0, len(grid[1][0])-i-2)) {
  77.         oc++;
  78.         idx = i;
  79.       }
  80.     }
  81.     if (oc == 0) {
  82.       cout << "NONE\n";
  83.     } else if (oc > 1) {
  84.       cout << "MANY\n";
  85.     } else {
  86.       cout << "UNIQUE\n";
  87.       cout << grid[0][1].substr(0, idx+1) << endl;
  88.       cout << grid[1][0].substr(0, len(grid[0][1])-idx-1) << endl;
  89.     }
  90.   } else {
  91.     ll sum = 0;
  92.     vector<ll> sumRow(n, 0LL);
  93.     forn(i, n) {
  94.       forn (j, n) {
  95.         if (i == j) continue;
  96.         sum += len(grid[i][j]);
  97.         sumRow[i] += len(grid[i][j]);
  98.       }
  99.     }
  100.  
  101.     sum /= ((2*n)-2);
  102.     vector<string> ans;
  103.     bool ok = true;
  104.     forn(i, n) {
  105.       ll strLen = (sumRow[i]-sum)/(n-2);
  106.       string o = "";
  107.       if (strLen <= 0) {
  108.         ok = false;
  109.         break;
  110.       }
  111.       forn(j, strLen) {
  112.         o += grid[i][(i+1)%n][j];
  113.       }
  114.       ans.push_back(o);
  115.     }
  116.  
  117.     if (len(ans) != n) {
  118.       cout << "NONE\n";
  119.       return;
  120.     }
  121.  
  122.     forn(i, n) {
  123.       forn(j, n) {
  124.         if (i == j) continue;
  125.         if (ans[i]+ans[j] != grid[i][j]) {
  126.           ok = false;
  127.           break;
  128.         }
  129.       }
  130.     }
  131.  
  132.     if (!ok) {
  133.       cout << "NONE\n";
  134.       return;
  135.     }
  136.     cout << "UNIQUE\n";
  137.     for (auto y: ans) cout << y << endl;
  138.   }
  139. }
  140.  
  141. int main()
  142. {
  143.   fast;
  144.  
  145.   int t = 1;
  146.   //cin >> t;
  147.  
  148.   while (t--)
  149.   {
  150.     solve();
  151.   }
  152.  
  153.   return 0;
  154. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
UNIQUE
https://ideone.com/rrdB0K
language:
C++ (gcc 8.3)
created:
13 days ago
visibility:
public

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!