oj.uz

Submission #240923

# Submission time Handle Problem Language Result Execution time Memory
240923 2020-06-21T13:38:14 Z SamAnd Osmosmjerka (COCI17_osmosmjerka) C++17
140 / 160
 4000 ms 245664 KB 
#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 = 891641833;
const int P = 307;

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;
        if (k > 0)
            astt = fast(P, (1 << (k - 1)));
        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];
                        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<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);
    solv();
    return 0;
}

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

Compilation message

osmosmjerka.cpp: In function 'void solv()':
osmosmjerka.cpp:133: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]);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
140.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 6 ms 1792 KB Output is correct
4 Correct 11 ms 3456 KB Output is correct
5 Correct 24 ms 6912 KB Output is correct
6 Correct 106 ms 20600 KB Output is correct
7 Correct 1206 ms 83232 KB Output is correct
8 Execution timed out 4090 ms 245664 KB Time limit exceeded