Submission #436305

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
436305	2021-06-24T12:14:20 Z	codebuster_10	Sateliti (COCI20_satellti)	C++17	110 / 110	634 ms	41940 KB

Main

#include <bits/stdc++.h>
using namespace std;

#define f(i,a,b) for(int i=int(a);i<int(b);++i)

#define vt vector
#define pb push_back


template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}




















/*
	* description :- polynomial hashing of strings.
	* sources :- https://codeforces.com/contest/710/submission/102996468
	* verification :- https://codeforces.com/contest/154/submission/120344887
*/






#ifdef int
	static_assert(false,"do not define int");
#endif




template<const unsigned &MOD>
struct _m_uint {
  unsigned val;
 
	_m_uint(int64_t v = 0) {
		if(v < 0) v = v % MOD + MOD;
    if(v >= MOD) v %= MOD;
    val = unsigned(v);
  }
 
	_m_uint(uint64_t v) {
  	if(v >= MOD) v %= MOD;
    val = unsigned(v);
  }
 
  _m_uint(int v) : _m_uint(int64_t(v)) {}
  _m_uint(unsigned v) : _m_uint(uint64_t(v)) {}
 
  explicit operator unsigned() const { return val; }
  explicit operator int64_t() const { return val; }
  explicit operator uint64_t() const { return val; }
  explicit operator double() const { return val; }
  explicit operator long double() const { return val; }
 
  _m_uint& operator+=(const _m_uint &other) {
  	val = val < MOD - other.val ? val + other.val : val - (MOD - other.val);
    return *this;
  }
 
  _m_uint& operator-=(const _m_uint &other) {
  	val = val < other.val ? val + (MOD - other.val) : val - other.val;
    return *this;
  }
 
  static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
  	return unsigned(x % m);
#endif
    // Optimized mod for Codeforces 32-bit machines.
    // x must be less than 2^32 * m for this to work, so that x / m fits in an unsigned 32-bit int.
    unsigned x_high = unsigned(x >> 32), x_low = unsigned(x);
    unsigned quot, rem;
    asm("divl %4\n"
    		: "=a" (quot), "=d" (rem)
        : "d" (x_high), "a" (x_low), "r" (m));
    return rem;
  }
 
  _m_uint& operator*=(const _m_uint &other) {
  	val = fast_mod(uint64_t(val) * other.val);
    return *this;
  }
 
  _m_uint& operator/=(const _m_uint &other) {
  	return *this *= other.inv();
  }
 
  friend _m_uint operator+(const _m_uint &a, const _m_uint &b) { return _m_uint(a) += b; }
  friend _m_uint operator-(const _m_uint &a, const _m_uint &b) { return _m_uint(a) -= b; }
  friend _m_uint operator*(const _m_uint &a, const _m_uint &b) { return _m_uint(a) *= b; }
  friend _m_uint operator/(const _m_uint &a, const _m_uint &b) { return _m_uint(a) /= b; }
 
  _m_uint& operator++() {
  	val = val == MOD - 1 ? 0 : val + 1;
    return *this;
  }
 
  _m_uint& operator--() {
  	val = val == 0 ? MOD - 1 : val - 1;
    return *this;
  }
 		
  _m_uint operator++(int) { _m_uint before = *this; ++*this; return before; }
  _m_uint operator--(int) { _m_uint before = *this; --*this; return before; }
 			
  _m_uint operator-() const {
  	return val == 0 ? 0 : MOD - val;
  }
 
  friend bool operator==(const _m_uint &a, const _m_uint &b) { return a.val == b.val; }
  friend bool operator!=(const _m_uint &a, const _m_uint &b) { return a.val != b.val; }
  friend bool operator<(const _m_uint &a, const _m_uint &b) { return a.val < b.val; }
  friend bool operator>(const _m_uint &a, const _m_uint &b) { return a.val > b.val; }
  friend bool operator<=(const _m_uint &a, const _m_uint &b) { return a.val <= b.val; }
  friend bool operator>=(const _m_uint &a, const _m_uint &b) { return a.val >= b.val; }
 
  static const int SAVE_INV = int(1e6) + 5;
  static _m_uint save_inv[SAVE_INV];
 
  static void prepare_inv() {
  	// Make sure MOD is prime, which is necessary for the inverse algorithm below.
    for(int64_t p = 2; p * p <= MOD; p += p % 2 + 1){
    	assert(MOD % p != 0);
    }	
 			
 		save_inv[0] = 0;
    save_inv[1] = 1;
 
    for (int i = 2; i < SAVE_INV; i++){
    	save_inv[i] = save_inv[MOD % i] * (MOD - MOD / i);
    }
  }
 
  _m_uint inv() const {
    if(save_inv[1] == 0)	prepare_inv();
 
    if(val < SAVE_INV)	return save_inv[val];
 
    _m_uint product = 1;
    unsigned v = val;
 
    while (v >= SAVE_INV) {
      product *= MOD - MOD / v;
      v = MOD % v;
    }
 
    return product * save_inv[v];
  }
 
  _m_uint pow(int64_t p) const {
  	if (p < 0)	return inv().pow(-p);
 
    _m_uint a = *this, result = 1;
 
    while(p > 0) {
      if(p & 1)	result *= a;
 			p >>= 1;
 			if(p > 0)	a *= a;
  	}
  	
    return result;
  }
 
  friend ostream& operator<<(ostream &os, const _m_uint &m) {
  	return os << m.val;
  }
};
 
template<const unsigned &MOD> _m_uint<MOD> _m_uint<MOD>::save_inv[_m_uint<MOD>::SAVE_INV];

auto random_address = [] { char *p = new char; delete p; return uint64_t(p); };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1));
 
// P = 2^32 - 13337 is a safe prime: both P and (P - 1) / 2 are prime.
extern const unsigned HASH_P = unsigned(-13337); // hash prime
using hash_int = _m_uint<HASH_P>;
using hash_t = uint64_t;

const uint64_t HASH_P2 = uint64_t(HASH_P) * HASH_P;// square of hash prime
const int HASH_COUNT = 2;
 
// Avoid multiplication bases near 0 or P - 1.
uniform_int_distribution<unsigned> MULT_DIST(unsigned(0.1 * HASH_P), unsigned(0.9 * HASH_P));
const hash_int HASH_MULT[] = {MULT_DIST(rng), MULT_DIST(rng)}; // our bases
const hash_int HASH_INV[] = {1 / HASH_MULT[0], 1 / HASH_MULT[1]};
 
vector<hash_int> hash_pow[] = {{1}, {1}};
 
const int INF = int(1e9) + 5;
 
template<typename T_string = string>
struct string_hash {
	static const bool BUILD_REVERSE = false;
 
  static uint64_t hash(const T_string &str) {
  	uint64_t result = 0;
 
    for(int h = 0; h < HASH_COUNT; h++) {
      uint64_t value = 1;
 			for(const auto &x : str){
 				value = (uint64_t(HASH_MULT[h]) * value + x) % HASH_P;
 			}
    
    	result += value << (32 * h);
   	}
 
  	return result;
  }
 
  T_string str;
  vector<hash_int> _prefix[HASH_COUNT];
  vector<hash_int> _inv_prefix[HASH_COUNT];
 
  string_hash() {
  	build({});
  }
 
  string_hash(const T_string &_str) {
  	build(_str);
  }
 
  int length() const {
  	return int(_prefix[0].size()) - 1;
  }
 
  template<typename T_char>
  void add_char(const T_char &c) {
  	str.push_back(c);
 
    for(int h = 0; h < HASH_COUNT; h++) {
    	_prefix[h].push_back(HASH_MULT[h] * _prefix[h].back() + c);
 
      if(hash_pow[h].size() < _prefix[h].size()){
      	hash_pow[h].push_back(HASH_MULT[h] * hash_pow[h].back());
 			}
 			
    	if(BUILD_REVERSE){
    		_inv_prefix[h].push_back((_inv_prefix[h].back() + c) * HASH_INV[h]);
    	}
                
    }
  }
 
  void pop_char() {
  	str.pop_back();
 
    for(int h = 0; h < HASH_COUNT; h++) {
    	_prefix[h].pop_back();
 
      if(BUILD_REVERSE) {
      	_inv_prefix[h].pop_back();
      }
                
    }
  }
 
  void build(const T_string &_str) {
  	str = {};
    str.reserve(_str.size());
 
    for(int h = 0; h < HASH_COUNT; h++) {
    	hash_pow[h].reserve(_str.size() + 1);
      _prefix[h] = {0};
      _prefix[h].reserve(_str.size() + 1);
 
      if(BUILD_REVERSE) {
      	_inv_prefix[h] = {0};
        _inv_prefix[h].reserve(_str.size() + 1);
      }
  	}
 
    for(auto &c : _str)	add_char(c);
  }
 
  uint64_t _single_hash(int h, int start, int end) const {
  	// Convert everything to `uint64_t` for speed. Note: we add hash_pow[length] to fix strings that start with 0.
    uint64_t power = uint64_t(hash_pow[h][end - start]);
  	return (power + uint64_t(_prefix[h][end]) + HASH_P2 - uint64_t(_prefix[h][start]) * power) % HASH_P;
  }
 
  uint64_t substring_hash(int start, int end) const {
  	assert(0 <= start && start <= end && end <= length());
    return _single_hash(0, start, end) + (HASH_COUNT > 1 ? _single_hash(1, start, end) << 32 : 0);
  }
 
  uint64_t complete_hash() const {
    return substring_hash(0, length());
  }
 
  uint64_t _reverse_single_hash(int h, int start, int end) const {
    // Convert everything to `uint64_t` for speed. Note: we add hash_pow[length] to fix strings that start with 0.
    uint64_t power = uint64_t(hash_pow[h][end - start]);
    return (power + uint64_t(_inv_prefix[h][end]) * power + HASH_P - uint64_t(_inv_prefix[h][start])) % HASH_P;
  }
 
  uint64_t reverse_substring_hash(int start, int end) const {
    assert(0 <= start && start <= end && end <= length());
    return _reverse_single_hash(0, start, end) + (HASH_COUNT > 1 ? _reverse_single_hash(1, start, end) << 32 : 0);
  }
 
  uint64_t reverse_complete_hash() const {
    return reverse_substring_hash(0, length());
  }
 
  bool equal(int start1, int start2, int length) const {
  	return substring_hash(start1, start1 + length) == substring_hash(start2, start2 + length);
  }
 
  bool is_palindrome(int start, int end) const {
    return substring_hash(start, end) == reverse_substring_hash(start, end);
  }
 
  int compare(int start1, int start2, int max_length = INF) const;
};
 
uint64_t concat_hashes(uint64_t hash1, uint64_t hash2, int len2) {
  uint64_t hash1_low = hash1 & unsigned(-1);
  uint64_t hash2_low = hash2 & unsigned(-1);
  uint64_t power = uint64_t(hash_pow[0][len2]);
  uint64_t combined = (hash1_low * power + hash2_low + HASH_P - power) % HASH_P;
 
  if (HASH_COUNT > 1) {
    hash1 >>= 32;
    hash2 >>= 32;
    power = uint64_t(hash_pow[1][len2]);
    combined += (hash1 * power + hash2 + HASH_P - power) % HASH_P << 32;
  }
 
  return combined;
}
 
template<typename T_string>
int first_mismatch(const string_hash<T_string> &hash1, int start1,
                   const string_hash<T_string> &hash2, int start2, int max_length = INF) {
	max_length = min({max_length, hash1.length() - start1, hash2.length() - start2});
 
  static const int FIRST = 5;
  int first = min(max_length, FIRST);
 
  for(int i = 0; i < first; i++){
  	if(hash1.str[start1 + i] != hash2.str[start2 + i]){
  		return i;
  	}
  }
        
 
  if(hash1.substring_hash(start1, start1 + max_length) == hash2.substring_hash(start2, start2 + max_length)){
  	return max_length;
 	}
 	
  static const int MANUAL = 15;
  int low = first, high = max_length - 1;
 
  while(high - low > MANUAL) {
  	int mid = (low + high + 1) / 2;
		if(hash1.substring_hash(start1, start1 + mid) == hash2.substring_hash(start2, start2 + mid)){
			low = mid;
		}else{
      high = mid - 1;
    }
  }
 
  for(int i = low; i < high; i++) {
    if(hash1.str[start1 + i] != hash2.str[start2 + i]){
    	return i;
    }
  }
 
  return high;
}
 
template<typename T_string>
int hash_compare(const string_hash<T_string> &hash1, int start1,
                 const string_hash<T_string> &hash2, int start2, int max_length = INF) {
  int mismatch = first_mismatch(hash1, start1, hash2, start2, max_length);
  int length1 = min(hash1.length() - start1, max_length);
  int length2 = min(hash2.length() - start2, max_length);
 
  if(mismatch == min(length1, length2)){
  	return length1 == length2 ? 0 : (length1 < length2 ? -1 : +1);
  }
        
 
  if(hash1.str[start1 + mismatch] == hash2.str[start2 + mismatch]){
  	return 0;
  }
        
 
  return hash1.str[start1 + mismatch] < hash2.str[start2 + mismatch] ? -1 : +1;
}
 
template<typename T_string>
int string_hash<T_string>::compare(int start1, int start2, int max_length) const {
  return hash_compare(*this, start1, *this, start2, max_length);
}





template<class T>	struct compress_1d_co_ordinates {
	
	vector<T> values;
	
  void add(T x){
  	values.push_back(x);
  	return;
  }
  
  void gen(){
  	sort(values.begin(),values.end());
  	values.erase(unique(values.begin(),values.end()),values.end());
  	return;
  }
  
  int get(T x){
  	int j = lower_bound(values.begin(),values.end(),x) - values.begin();
  	assert(values[j] == x); return j;
  }
  
  void clear(){
  	values.clear();
  	return;
  }
  
};








signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  
  int n,m; rd(n,m);
  vector<string> s(n);
  rd(s);
  
  string_hash<string> string_h[2*n];
  
  f(i,0,n){
  	string_h[i].build(s[i]+s[i]);
  	string_h[i+n].build(s[i]+s[i]);
  }
  
  
  
  vt<int> best(m); 
  
  // rotote horizontally
  for(int i = 0; i < m; ++i){
  	vt<hash_t> _strings(2*n);
  	vt<int> strings;
  	
  	compress_1d_co_ordinates<hash_t> compress; 
  	
  	for(int j = 0; j < n; ++j){
  		_strings[j] = _strings[n+j] = string_h[j].substring_hash(i,i+m);		
  		compress.add(_strings[j]);
  	}
  	
  	compress.gen();
  	
  	for(auto& i : _strings) strings.pb(compress.get(i));
  	
  	compress.clear();
  	
  	string_hash<vector<int>> vector_h;
  	vector_h.build(strings);
  	
  	int current_best = 0;
  	for(int j = 1; j < n; ++j){
  		int k = first_mismatch(vector_h,current_best,vector_h,j,n);
  		if(k == n) continue;
  		
  		int c = hash_compare(string_h[current_best+k],i,string_h[j+k],i,m);
  		
  		assert(c != 0);
  		
  		// if string 2 is small.
  		if(c == 1)	current_best = j;
  		
  	}
  	
  	best[i] = current_best;
  	
  	
  }
  
  int x = 0;
  for(int i = 1; i < m; ++i){
  	for(int j = 0; j < n; ++j){
  		if(string_h[best[x] + j].substring_hash(x,x+m) != string_h[best[i] + j].substring_hash(i,i+m)){
  			int c = hash_compare(string_h[best[x] + j],x,string_h[best[i] + j],i,m);
  			
  			assert(c != 0);
  			
  			// if string 2 is small
  			
  			if(c == 1)	x = i;
  			break;
  		}
  	}
  }
  

  
  f(i,0,n){
  	f(j,0,m){
  		cout << s[(i+best[x])%n][(j+x)%m];
  	}
  	cout << "\n";
  }
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	4300 KB	Output is correct
2	Correct	12 ms	4300 KB	Output is correct
3	Correct	19 ms	4248 KB	Output is correct
4	Correct	20 ms	4280 KB	Output is correct
5	Correct	12 ms	4324 KB	Output is correct
6	Correct	13 ms	4328 KB	Output is correct
7	Correct	11 ms	4332 KB	Output is correct

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	4300 KB	Output is correct
2	Correct	12 ms	4300 KB	Output is correct
3	Correct	19 ms	4248 KB	Output is correct
4	Correct	20 ms	4280 KB	Output is correct
5	Correct	12 ms	4324 KB	Output is correct
6	Correct	13 ms	4328 KB	Output is correct
7	Correct	11 ms	4332 KB	Output is correct
8	Correct	45 ms	7504 KB	Output is correct
9	Correct	12 ms	4344 KB	Output is correct
10	Correct	11 ms	4324 KB	Output is correct
11	Correct	38 ms	7516 KB	Output is correct
12	Correct	47 ms	7500 KB	Output is correct
13	Correct	38 ms	7712 KB	Output is correct
14	Correct	46 ms	7620 KB	Output is correct
15	Correct	46 ms	7628 KB	Output is correct
16	Correct	67 ms	7628 KB	Output is correct
17	Correct	60 ms	7632 KB	Output is correct

Subtask #3

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	4300 KB	Output is correct
2	Correct	12 ms	4300 KB	Output is correct
3	Correct	19 ms	4248 KB	Output is correct
4	Correct	20 ms	4280 KB	Output is correct
5	Correct	12 ms	4324 KB	Output is correct
6	Correct	13 ms	4328 KB	Output is correct
7	Correct	11 ms	4332 KB	Output is correct
8	Correct	45 ms	7504 KB	Output is correct
9	Correct	12 ms	4344 KB	Output is correct
10	Correct	11 ms	4324 KB	Output is correct
11	Correct	38 ms	7516 KB	Output is correct
12	Correct	47 ms	7500 KB	Output is correct
13	Correct	38 ms	7712 KB	Output is correct
14	Correct	46 ms	7620 KB	Output is correct
15	Correct	46 ms	7628 KB	Output is correct
16	Correct	67 ms	7628 KB	Output is correct
17	Correct	60 ms	7632 KB	Output is correct
18	Correct	514 ms	41836 KB	Output is correct
19	Correct	17 ms	5056 KB	Output is correct
20	Correct	20 ms	4940 KB	Output is correct
21	Correct	513 ms	41940 KB	Output is correct
22	Correct	578 ms	41836 KB	Output is correct
23	Correct	491 ms	41848 KB	Output is correct
24	Correct	535 ms	41852 KB	Output is correct
25	Correct	486 ms	41848 KB	Output is correct
26	Correct	634 ms	41924 KB	Output is correct
27	Correct	590 ms	41796 KB	Output is correct