Submission #240919

#	Time	Username	Problem	Language	Result	Execution time	Memory
240919		SamAnd	Osmosmjerka (COCI17_osmosmjerka)	C++17	140 / 160	1555 ms	262144 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 pair<int, int> M = m_p(891641833, 716000533);
const int P = 307;

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

pair<int, int> sum(const pair<int, int>& a, const pair<int, int>& b)
{
    return m_p((a.fi + b.fi) % M.fi, (a.se + b.se) % M.se);
}

pair<int, int> dif(const pair<int, int>& a, const pair<int, int>& b)
{
    return m_p((a.fi - b.fi + M.fi) % M.fi, (a.se - b.se + M.se) % M.se);
}

pair<int, int> pro(const pair<int, int>& a, const pair<int, int>& b)
{
    return m_p((a.fi * 1LL * b.fi) % M.fi, (a.se * 1LL * b.se) % M.se);
}

pair<int, int> ast[N];
void pre()
{
    ast[0] = m_p(1, 1);
    for (int i = 1; i < N; ++i)
        ast[i] = pro(ast[i - 1], m_p(P, P));
}

pair<int, int> fast(pair<int, int> x, int n)
{
    pair<int, int> ans = m_p(1, 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];

pair<int, 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)
    {
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                pair<int, int> astt = fast(m_p(P, P), (1 << (k - 1)));
                for (int u = 0; u < 8; ++u)
                {
                    if (k == 0)
                    {
                        h[k][i][j][u] = m_p(a[i][j], a[i][j]);
                        continue;
                    }
                    int i1 = (i + xx[u] * (1 << (k - 1))) % n;
                    int j1 = (j + yy[u] * (1 << (k - 1))) % m;
                    i1 = (i1 + n) % n;
                    j1 = (j1 + m) % 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<pair<int, 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;
                pair<int, int> hh = m_p(0, 0);
                int q = 0;
                for (int b = 0; b < 30; ++b)
                {
                    if ((k & (1 << b)))
                    {
                        hh = sum(hh, pro(fast(m_p(P, 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);
    solv();
    return 0;
}

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

Compilation message (stderr)

osmosmjerka.cpp: In function 'void solv()':
osmosmjerka.cpp:139:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < v.size(); ++i)
                     ~~^~~~~~~~~~
osmosmjerka.cpp:78: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:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", a[i]);
         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 140 / 160