Submission #436310

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
436310	2021-06-24T12:15:51 Z	codebuster_10	Sateliti (COCI20_satellti)	C++17	110 / 110	755 ms	41952 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	20 ms	4300 KB	Output is correct
2	Correct	22 ms	4284 KB	Output is correct
3	Correct	13 ms	4300 KB	Output is correct
4	Correct	14 ms	4212 KB	Output is correct
5	Correct	14 ms	4240 KB	Output is correct
6	Correct	12 ms	4324 KB	Output is correct
7	Correct	13 ms	4288 KB	Output is correct

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	4300 KB	Output is correct
2	Correct	22 ms	4284 KB	Output is correct
3	Correct	13 ms	4300 KB	Output is correct
4	Correct	14 ms	4212 KB	Output is correct
5	Correct	14 ms	4240 KB	Output is correct
6	Correct	12 ms	4324 KB	Output is correct
7	Correct	13 ms	4288 KB	Output is correct
8	Correct	45 ms	7504 KB	Output is correct
9	Correct	25 ms	4272 KB	Output is correct
10	Correct	12 ms	4300 KB	Output is correct
11	Correct	61 ms	7492 KB	Output is correct
12	Correct	57 ms	7492 KB	Output is correct
13	Correct	48 ms	7704 KB	Output is correct
14	Correct	46 ms	7620 KB	Output is correct
15	Correct	44 ms	7624 KB	Output is correct
16	Correct	53 ms	7676 KB	Output is correct
17	Correct	51 ms	7644 KB	Output is correct

Subtask #3

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	4300 KB	Output is correct
2	Correct	22 ms	4284 KB	Output is correct
3	Correct	13 ms	4300 KB	Output is correct
4	Correct	14 ms	4212 KB	Output is correct
5	Correct	14 ms	4240 KB	Output is correct
6	Correct	12 ms	4324 KB	Output is correct
7	Correct	13 ms	4288 KB	Output is correct
8	Correct	45 ms	7504 KB	Output is correct
9	Correct	25 ms	4272 KB	Output is correct
10	Correct	12 ms	4300 KB	Output is correct
11	Correct	61 ms	7492 KB	Output is correct
12	Correct	57 ms	7492 KB	Output is correct
13	Correct	48 ms	7704 KB	Output is correct
14	Correct	46 ms	7620 KB	Output is correct
15	Correct	44 ms	7624 KB	Output is correct
16	Correct	53 ms	7676 KB	Output is correct
17	Correct	51 ms	7644 KB	Output is correct
18	Correct	524 ms	41716 KB	Output is correct
19	Correct	16 ms	5068 KB	Output is correct
20	Correct	24 ms	4940 KB	Output is correct
21	Correct	523 ms	41952 KB	Output is correct
22	Correct	583 ms	41932 KB	Output is correct
23	Correct	604 ms	41848 KB	Output is correct
24	Correct	546 ms	41924 KB	Output is correct
25	Correct	755 ms	41848 KB	Output is correct
26	Correct	689 ms	41848 KB	Output is correct
27	Correct	607 ms	41800 KB	Output is correct