Submission #444664

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
444664	2021-07-14T14:37:05 Z	233	Osmosmjerka (COCI17_osmosmjerka)	C++11	160 / 160	2728 ms	95420 KB

osmosmjerka

#include <cstdio>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <cstdlib>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long llint;
typedef pair <int, int> pii;

const int MAXN = 505;
const int MAXLOG = 31;
const int MAXK = 2;

int n, m, k;
char str[MAXN][MAXN];
int base_pow2[MAXK][MAXLOG];

const int bases[MAXK] = {3137, 51518};
const int modulo[MAXK] = {(int)((1e9) + 7), 999999937};

struct hashed_string {
    int hashes[MAXK];
    hashed_string() {
        memset(hashes, 0, sizeof hashes);
    }
    void append(const hashed_string &a, int pow2len) {
        for (int i = 0; i < MAXK; ++i) {
            hashes[i] = ((llint)hashes[i] * base_pow2[i][pow2len]) % modulo[i] + a.hashes[i];
            if (hashes[i] >= modulo[i]) hashes[i] -= modulo[i];
        }
    }
};

bool operator < (const hashed_string &a, const hashed_string &b) {
    for (int i = 0; i < 2; ++i)
        if (a.hashes[i] != b.hashes[i]) return a.hashes[i] < b.hashes[i];
    return 0;
}

map <hashed_string, int> M;

hashed_string field[MAXLOG][MAXN][MAXN];

void generate(int dx, int dy) {
    for (int i = 0; i < MAXK; ++i)
        base_pow2[i][0] = bases[i];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            for (int k = 0; k < MAXK; ++k)
                field[0][i][j].hashes[k] = str[i][j] % modulo[k];
    
    int len = 1;
    for (int log = 1; log < MAXLOG; ++log) {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                field[log][i][j] = field[log-1][i][j];
                field[log][i][j].append(field[log-1][((i + dx * len)%n + n)%n][((j + dy * len)%m + m)%m], log - 1);
            }
        for (int i = 0; i < MAXK; ++i)
            base_pow2[i][log] = (base_pow2[i][log-1] * (llint)base_pow2[i][log-1]) % modulo[i];
        len *= 2;
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            int len = k;
            hashed_string res;
            int cx, cy; cx = i; cy = j;
            for (int k = MAXLOG-1; k >= 0; --k) {
                if ((1 << k) <= len) {
                    len -= (1 << k);
                    res.append(field[k][cx][cy], k);
                    cx = ((cx + dx * (1 << k)) % n + n)%n;
                    cy = ((cy + dy * (1 << k)) % m + m)%m;
                }
            }
            M[res] += 1;
        }
}

int main (void){
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < n; ++i)
        scanf("%s", str[i]);
    for (int dx = -1; dx <= 1; ++dx)
        for (int dy = -1; dy <= 1; ++dy) {
            if (dx == 0 && dy == 0) continue;
            generate(dx, dy);
        }
    
    llint brojnik, nazivnik;
    brojnik = 0; nazivnik = (llint)(n * m * 8) * (n * m * 8);
    for (auto it: M)
        brojnik += it.second * (llint)it.second;
    llint g = __gcd(brojnik, nazivnik);
    brojnik /= g; nazivnik /= g;
    printf("%lld/%lld\n", brojnik, nazivnik);
    return 0;
}

Compilation message

osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     scanf("%d%d%d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
osmosmjerka.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         scanf("%s", str[i]);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1

160.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	62092 KB	Output is correct
2	Correct	28 ms	62152 KB	Output is correct
3	Correct	29 ms	62132 KB	Output is correct
4	Correct	30 ms	62244 KB	Output is correct
5	Correct	37 ms	62288 KB	Output is correct
6	Correct	89 ms	64952 KB	Output is correct
7	Correct	795 ms	81284 KB	Output is correct
8	Correct	2728 ms	95420 KB	Output is correct