제출 #436304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
436304		codebuster_10	Sateliti (COCI20_satellti)	C++17	110 / 110	678 ms	42956 KiB

Main

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

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60