Submission #140517

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
140517	2019-08-03T10:07:42 Z	Minnakhmetov	Osmosmjerka (COCI17_osmosmjerka)	C++14	160 / 160	1165 ms	64240 KB

osmosmjerka

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int MOD[2] = { (int)1e9 + 7, (int)1e9 + 9 }, X[2] = { 997, 1009 },
    N = 505, M = N * N;
ll p[2][M];

struct Hash {
    int len;
    pair<ll, ll> val, p;

    Hash() {
        len = 0;
        val = { 0, 0 };
        p = { 1, 1 };
    }

    Hash(char c) {
        len = 1;
        val = { c, c };
        p = { X[0], X[1] };
    }

    bool operator < (const Hash &oth) const {
        return val < oth.val;
    }
};

Hash operator + (Hash a, Hash b) {
    Hash c;
    c.len = a.len + b.len;

    c.val.first = (a.val.first * b.p.first + b.val.first) % MOD[0];
    c.val.second = (a.val.second * b.p.second + b.val.second) % MOD[1];

    c.p.first = a.p.first * b.p.first % MOD[0];
    c.p.second = a.p.second * b.p.second % MOD[1];

    return c;
}

Hash operator - (Hash a, Hash b) {
    Hash c;
    c.len = a.len - b.len;
    c.val.first = (a.val.first - b.val.first * p[0][c.len] % MOD[0] + MOD[0]) % MOD[0];
    c.val.second = (a.val.second - b.val.second * p[1][c.len] % MOD[1] + MOD[1]) % MOD[1];
    c.p = { p[0][c.len], p[1][c.len] };
    return c;
}

char s[N][N], t[N][N];
bool used[N][N];
Hash pref[M];

int n, m, k;

map<Hash, int> mp;


Hash bp(Hash h, int p) {
    Hash r;
    while (p > 0) {
        if (p & 1)
            r = r + h;
        h = h + h;
        p >>= 1;
    }
    return r;
}

void handle(string w) {
    int len = w.size();
    for (int i = 0; i < len; i++) {
        pref[i + 1] = pref[i] + Hash(w[i]);
    }

    Hash mid, beg;
    int last = -1;
    for (int i = len - 1; i >= 0; i--) {
        beg = Hash(w[i]) + beg;

        if (len >= k + i) {
            mp[pref[i + k] - pref[i]]++;
        }
        else {
            int whole = k - (len - i),
                rest = whole % len;
            whole /= len;

            if (last != whole) {
                last = whole;
                mid = bp(pref[len], whole);
            }

            mp[beg + mid + pref[rest]]++;
        }
    }
}

void solve(int n, int m, char a[N][N]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            used[i][j] = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        string w;
        for (int j = 0; j < m; j++) {
            if (!used[i][j]) {
                w.clear();

                int x = i, y = j;
                while (!used[x][y]) {
                    used[x][y] = 1;
                    w.push_back(a[x][y]);
                    x = (x + n - 1) % n;
                    y = (y + 1) % m;
                }

                handle(w);
                reverse(all(w));
                handle(w);
            }
        }


        w = a[i];
        handle(w);
        reverse(all(w));
        handle(w);
    }
}

ll gcd(ll a, ll b) {
    return a ? gcd(b % a, a) : b;
}

signed main() { 
#ifdef HOME
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 0; i < 2; i++) {
        p[i][0] = 1;
        for (int j = 1; j < M; j++) {
            p[i][j] = p[i][j - 1] * X[i] % MOD[i];
        }
    }

    cin >> n >> m >> k;

    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            t[j][n - i - 1] = s[i][j];
        }
    }


    solve(n, m, s);
    solve(m, n, t);

    ll p = 0, q = (ll)n * m * n * m * 64;

    for (auto &x : mp) {
        p += x.second * (ll)x.second;
    }

    ll g = gcd(p, q);

    p /= g;
    q /= g;

    cout << p << "/" << q;

    return 0;
}

Subtask #1

160.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	14456 KB	Output is correct
2	Correct	16 ms	14328 KB	Output is correct
3	Correct	16 ms	14456 KB	Output is correct
4	Correct	16 ms	14456 KB	Output is correct
5	Correct	18 ms	14584 KB	Output is correct
6	Correct	44 ms	18680 KB	Output is correct
7	Correct	403 ms	43284 KB	Output is correct
8	Correct	1165 ms	64240 KB	Output is correct