Submission #762841

#TimeUsernameProblemLanguageResultExecution timeMemory
762841PanosPaskOsmosmjerka (COCI17_osmosmjerka)C++14
120 / 160
4070 ms13400 KiB
#include <bits/stdc++.h> #define s second #define f first using namespace std; typedef long long ll; typedef __int128_t lll; struct StringHash { ll MOD = (1ll << 61) - 1; int P = 31; vector<ll> hash; vector<ll> pow; void init(string& st) { hash.resize(st.size() + 1); pow.resize(st.size() + 1); hash[0] = 0; pow[0] = 1; for (int i = 0; i < st.size(); i++) { hash[i + 1] = ((lll)hash[i] * P + st[i] - 'a' + 1) % MOD; pow[i + 1] = (lll)pow[i] * P % MOD; } } ll get(int l, int len) { int r = l + len - 1; lll res = hash[r + 1] - (lll)hash[l] * pow[len] % MOD; return ((res % MOD) + MOD) % MOD; } }; const int DIRS = 8; const int d_i[8] = {1, 0, -1, 0, 1, 1, -1, -1}; const int d_j[8] = {0, 1, 0, -1, 1, -1, 1, -1}; int n, m, k; vector<string> words; int len; vector<vector<bool>> visited; vector<ll> all; void generate_string(int or_i, int or_j, int d_i, int d_j) { string st; int cur = 0; int i = or_i; int j = or_j; int bomb = INT_MAX; // Create the string while (cur < n * m && cur < bomb) { st.push_back(words[i][j]); cur++; if (visited[i][j] || (i == or_i && j == or_j)) bomb = min(bomb, cur + len); i += d_i; j += d_j; i = (i + m) % m; j = (j + n) % n; } st = st + st; while (st.size() < 2 * len) st = st + st; // Hash the string and calculate it StringHash cur_hash; cur_hash.init(st); i = or_i; j = or_j; cur = 0; while (cur < n * m && !visited[i][j]) { all.push_back(cur_hash.get(cur, len)); visited[i][j] = true; cur++; i = i + d_i; j = j + d_j; i = (i + m) % m; j = (j + n) % n; } } int main(void) { ios::sync_with_stdio(false); cin >> m >> n >> k; len = min(n * m, k); words.resize(m); for (int i = 0; i < m; i++) cin >> words[i]; for (int x = 0; x < DIRS; x++) { visited.assign(m, vector<bool>(n, false)); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (!visited[i][j]) generate_string(i, j, d_i[x], d_j[x]); } } } ll total_combo = (8 * n * m) * (ll)(8 * n * m); ll total_same = 0; sort(all.begin(), all.end()); ll cur_num = -1; int cur_same = 0; for (int i = 0; i < all.size(); i++) { if (all[i] == cur_num) cur_same++; else { total_same += (ll)cur_same * cur_same; cur_num = all[i]; cur_same = 1; } } total_same += (ll)cur_same * cur_same; ll d = __gcd(total_combo, total_same); total_combo /= d; total_same /= d; cout << total_same << '/' << total_combo << endl; return 0; }

Compilation message (stderr)

osmosmjerka.cpp: In member function 'void StringHash::init(std::string&)':
osmosmjerka.cpp:24:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for (int i = 0; i < st.size(); i++) {
      |                         ~~^~~~~~~~~~~
osmosmjerka.cpp: In function 'void generate_string(int, int, int, int)':
osmosmjerka.cpp:73:22: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |     while (st.size() < 2 * len)
      |            ~~~~~~~~~~^~~~~~~~~
osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:127:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for (int i = 0; i < all.size(); i++) {
      |                     ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...