oj.uz

Submission #416684

# Submission time Handle Problem Language Result Execution time Memory
416684 2021-06-02T18:43:15 Z SirCovidThe19th Osmosmjerka (COCI17_osmosmjerka) C++14
80 / 160
 4000 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const ll p = 1663, mod = 1e9+7;
int di[8] = {0, 0, -1, 1, -1, -1, 1, 1}, dj[8] = {-1, 1, 0, 0, -1, 1, 1, -1};

ll bpow(ll a, ll b){
    if (b == 0) return 1;
    ll res = bpow(a, b/2)%mod; if (b%2 == 1) return (((res*res)%mod)*a)%mod; else return (res*res)%mod;
}

int main() {
    int n, m, k; cin >> n >> m >> k; 
    string grid[n]; ll vals[n][m][(int)floor(log2(k))+1][8]; map<ll, ll> eq;
    for (int i = 0; i < n; i++) cin >> grid[i];
    for (int l = 0; (1<<l) <= k; l++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int d = 0; d < 8; d++){
                    if (l == 0){ vals[i][j][l][d] = (grid[i][j]-'a'+1); continue;}
                    int r = (i+(((1<<(l-1)))*di[d])+500*n)%n, c = (j+(((1<<(l-1)))*dj[d])+500*m)%m;
                    vals[i][j][l][d] = (vals[i][j][l-1][d]+vals[r][c][l-1][d]*bpow(p, (1<<(l-1))))%mod;
                }
    deque<int> setBits; for (int i = 0; (1<<i) <= k; i++) if ((k>>i)%2 == 1) setBits.push_front(i);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int d = 0; d < 8; d++){
                ll hash = 0; int cnt = 0;
                for (int b = 0; b < setBits.size(); b++){
                    int r = (i+(cnt*di[d])+500*n)%n, c = (j+(cnt*dj[d])+500*m)%m;
                    hash = (hash+vals[r][c][setBits[b]][d]*bpow(p, cnt))%mod;
                    cnt += (1<<setBits[b]);
                }
                eq[hash]++;
            }
    ll good = 0, tot = (ll)(n*m*8)*(n*m*8);
    for (auto elem : eq) good += elem.second*elem.second; 
    ll div = __gcd(good, tot); cout<<good/div<<"/"<<tot/div;
}

Compilation message

osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:31:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |                 for (int b = 0; b < setBits.size(); b++){
      |                                 ~~^~~~~~~~~~~~~~~~

Subtask #1
80.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 716 KB Output is correct
5 Incorrect 33 ms 2540 KB Output isn't correct
6 Incorrect 294 ms 15648 KB Output isn't correct
7 Execution timed out 4061 ms 123132 KB Time limit exceeded
8 Runtime error 126 ms 262148 KB Execution killed with signal 9