oj.uz

답안 #436304

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
436304 2021-06-24T12:11:42 Z codebuster_10 Sateliti (COCI20_satellti) C++17
110 / 110
 678 ms 42956 KB 
#include <bits/stdc++.h>
using namespace std;

//#define int int64_t //be careful about this 
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)

#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound  
#define UB upper_bound
#define PQ priority_queue

#define SZ(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a, b, sizeof(a))

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) ;}

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

template<typename T>
void __p(T a) {
  cout<<a; 
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cout<<"{";
  __p(a.first);
  cout<<",";
  __p(a.second);
  cout<<"}\n"; 
}
template<typename T>
void __p(std::vector<T> a) {
  cout<<"{";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cout<<",}\n"[it+1==a.end()]; 
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout<<name<<" : ";
  __p(arg1);
  cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cout.write(names,comma-names)<<" : ";
  __p(arg1);
  cout<<" | ";
  __f(comma+1,args...);
}

void setIO(string s = "") {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  cin.exceptions(cin.failbit); 
	cout.precision(15);	cout << fixed;
  if(SZ(s)){
  	freopen((s+".in").c_str(),"r",stdin);
  	freopen((s+".out").c_str(),"w",stdout);
  }
}



























/*
	* 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(){
  setIO();
  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 << endl;
  }
}

Compilation message

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:83:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |    freopen((s+".in").c_str(),"r",stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:84:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |    freopen((s+".out").c_str(),"w",stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 4300 KB Output is correct
2 Correct 13 ms 4228 KB Output is correct
3 Correct 13 ms 4300 KB Output is correct
4 Correct 25 ms 4332 KB Output is correct
5 Correct 13 ms 4300 KB Output is correct
6 Correct 14 ms 4272 KB Output is correct
7 Correct 13 ms 4300 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 4300 KB Output is correct
2 Correct 13 ms 4228 KB Output is correct
3 Correct 13 ms 4300 KB Output is correct
4 Correct 25 ms 4332 KB Output is correct
5 Correct 13 ms 4300 KB Output is correct
6 Correct 14 ms 4272 KB Output is correct
7 Correct 13 ms 4300 KB Output is correct
8 Correct 46 ms 7644 KB Output is correct
9 Correct 13 ms 4324 KB Output is correct
10 Correct 15 ms 4352 KB Output is correct
11 Correct 40 ms 7604 KB Output is correct
12 Correct 47 ms 7596 KB Output is correct
13 Correct 43 ms 7708 KB Output is correct
14 Correct 59 ms 7776 KB Output is correct
15 Correct 45 ms 7724 KB Output is correct
16 Correct 54 ms 7724 KB Output is correct
17 Correct 51 ms 7716 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 4300 KB Output is correct
2 Correct 13 ms 4228 KB Output is correct
3 Correct 13 ms 4300 KB Output is correct
4 Correct 25 ms 4332 KB Output is correct
5 Correct 13 ms 4300 KB Output is correct
6 Correct 14 ms 4272 KB Output is correct
7 Correct 13 ms 4300 KB Output is correct
8 Correct 46 ms 7644 KB Output is correct
9 Correct 13 ms 4324 KB Output is correct
10 Correct 15 ms 4352 KB Output is correct
11 Correct 40 ms 7604 KB Output is correct
12 Correct 47 ms 7596 KB Output is correct
13 Correct 43 ms 7708 KB Output is correct
14 Correct 59 ms 7776 KB Output is correct
15 Correct 45 ms 7724 KB Output is correct
16 Correct 54 ms 7724 KB Output is correct
17 Correct 51 ms 7716 KB Output is correct
18 Correct 563 ms 42720 KB Output is correct
19 Correct 16 ms 5068 KB Output is correct
20 Correct 24 ms 4868 KB Output is correct
21 Correct 490 ms 42956 KB Output is correct
22 Correct 587 ms 42836 KB Output is correct
23 Correct 506 ms 42852 KB Output is correct
24 Correct 520 ms 42832 KB Output is correct
25 Correct 456 ms 42820 KB Output is correct
26 Correct 678 ms 42832 KB Output is correct
27 Correct 613 ms 42776 KB Output is correct