Submission #436310

#	Time	Username	Problem	Language	Result	Execution time	Memory
436310		codebuster_10	Sateliti (COCI20_satellti)	C++17	110 / 110	755 ms	41952 KiB

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