Submission #762859

#	Time	Username	Problem	Language	Result	Execution time	Memory
762859		PanosPask	Osmosmjerka (COCI17_osmosmjerka)	C++17	140 / 160	4045 ms	17520 KiB

osmosmjerka

#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 = 4;
const int d_i[4] = {1, 0, 1, 1};
const int d_j[4] = {0, 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 beg;

    int cur = 0;
    int i = or_i;
    int j = or_j;
    // Create the string
    while (cur == 0 || (i != or_i) || (j != or_j)) {
        beg.push_back(words[i][j]);
        cur++;

        i += d_i;
        j += d_j;

        i = (i + m) % m;
        j = (j + n) % n;
    }

    string b2 = beg;
    reverse(b2.begin(), b2.end());

    string st = beg + beg;
    string st2 = b2 + b2;
    while (st.size() < cur + len - 1) {
        st += beg;
        st2 += b2;
    }
    // Hash the string and calculate it

    StringHash cur_hash;
    cur_hash.init(st);
    StringHash cur_hash2;
    cur_hash2.init(st2);

    i = or_i;
    j = or_j;
    cur = 0;
    while (!visited[i][j]) {
        all.push_back(cur_hash.get(cur, len));
        all.push_back(cur_hash2.get(cur, len));
        visited[i][j] = true;
        cur++;

        i = i + d_i;
        j = j + d_j;

        i = (i + m) % m;
        j = (j + n) % n;
    }
}

ll gcd(ll a, ll b)
{
    while (b != 0) {
        swap(b, a %= b);
    }

    return a;
}

int main(void)
{
    cin >> m >> n >> k;

    len = min(n * m, k);

    words.resize(m);

    for (int i = 0; i < m; i++) {
        words[i].resize(n);
        for (int j = 0; j < n; j++)
            scanf(" %c", &words[i][j]);
    }

    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;

    printf("%lld/%lld\n", total_same, total_combo);

    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() < cur + len - 1) {
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~
osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:142:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for (int i = 0; i < all.size(); i++) {
      |                     ~~^~~~~~~~~~~~
osmosmjerka.cpp:121:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |             scanf(" %c", &words[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 160