Submission #240928

#	Time	Username	Problem	Language	Result	Execution time	Memory
240928		SamAnd	Osmosmjerka (COCI17_osmosmjerka)	C++17	160 / 160	3773 ms	245376 KiB

osmosmjerka

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 503;
const int xx[8] = {0, 1, 0, -1, 1, -1, 1, -1};
const int yy[8] = {1, 0, -1, 0, 1, -1, -1, 1};

const int M = 1000000009;
const int P = 31;

bool prime(int x)
{
    for (int i = 2; i * i <= x; ++i)
    {
        if (x % i == 0)
            return false;
    }
    return true;
}

int sum(const int& a, const int& b)
{
    return (a + b) % M;
}

int dif(const int& a, const int& b)
{
    return (a - b + M) % M;
}

int pro(const int& a, const int& b)
{
    return (a * 1LL * b) % M;
}

int fast(int x, int n)
{
    int ans = 1;
    while (n)
    {
        if (n % 2 == 1)
            ans = pro(ans, x);
        x = pro(x, x);
        n /= 2;
    }
    return ans;
}

ll gcd(ll x, ll y)
{
    if (x == 0)
        return y;
    return gcd(y % x, x);
}

int n, m, k;
char a[N][N];

int h[30][N][N][8];

void solv()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < n; ++i)
    {
        scanf(" %s", a[i]);
    }
    for (int k = 0; k < 30; ++k)
    {
        int astt;
        int nn, mm;
        if (k > 0)
        {
            astt = fast(P, (1 << (k - 1)));
            nn = (1 << (k - 1)) % n;
            mm = (1 << (k - 1)) % m;
        }
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                for (int u = 0; u < 8; ++u)
                {
                    if (k == 0)
                    {
                        h[k][i][j][u] = a[i][j] - 'a' + 1;
                        continue;
                    }
                    int i1 = (i + xx[u] * nn);
                    int j1 = (j + yy[u] * mm);
                    if (i1 >= n)
                        i1 -= n;
                    else if (i1 < 0)
                        i1 += n;
                    if (j1 >= m)
                        j1 -= m;
                    else if (j1 < 0)
                        j1 += m;
                    h[k][i][j][u] = sum(h[k - 1][i][j][u], pro(h[k - 1][i1][j1][u], astt));
                }
            }
        }
    }
    ll ham = 0;
    ll hay = (n * m * 8) * 1LL * (n * m * 8);
    vector<int> v;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            for (int u = 0; u < 8; ++u)
            {
                int i1 = i;
                int j1 = j;
                int hh = 0;
                int q = 0;
                for (int b = 0; b < 30; ++b)
                {
                    if ((k & (1 << b)))
                    {
                        hh = sum(hh, pro(fast(P, q), h[b][i][j][u]));
                        q += (1 << b);
                        i = (i + xx[u] * (1 << b)) % n;
                        j = (j + yy[u] * (1 << b)) % m;
                        i = (i + n) % n;
                        j = (j + m) % m;
                    }
                }
                v.push_back(hh);
                i = i1;
                j = j1;
            }
        }
    }
    sort(all(v));
    int q = 1;
    for (int i = 1; i < v.size(); ++i)
    {
        if (v[i] == v[i - 1])
            ++q;
        else
        {
            ham += q * 1LL * q;
            q = 1;
        }
    }
    ham += q * 1LL * q;
    ll g = gcd(ham, hay);
    ham /= g;
    hay /= g;
    printf("%lld/%lld\n", ham, hay);
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    /*int x = 999999900;
    while (!prime(x))
    {
        ++x;
    }
    printf("%d\n", x);*/
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message (stderr)

osmosmjerka.cpp: In function 'void solv()':
osmosmjerka.cpp:144:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < v.size(); ++i)
                     ~~^~~~~~~~~~
osmosmjerka.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
osmosmjerka.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", a[i]);
         ~~~~~^~~~~~~~~~~~~
osmosmjerka.cpp:97:41: warning: 'mm' may be used uninitialized in this function [-Wmaybe-uninitialized]
                     int j1 = (j + yy[u] * mm);
                                   ~~~~~~^~~~
osmosmjerka.cpp:96:41: warning: 'nn' may be used uninitialized in this function [-Wmaybe-uninitialized]
                     int i1 = (i + xx[u] * nn);
                                   ~~~~~~^~~~

• Subtask 1: 160 / 160