Submission #533793

#	Time	Username	Problem	Language	Result	Execution time	Memory
533793		stefantaga	Osmosmjerka (COCI17_osmosmjerka)	C++14	160 / 160	3211 ms	186224 KiB

osmosmjerka

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma target("tune=native")
//#define int long long
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
const int N = 500, P[2] = {10, 31}, mod[2] = {1000000000 + 7, 999999937};
int n, m, k;
string s[N];
ll hs[N][N][31][2], deg[31][2];
 
int dx, dy;
 
void make_hash(){
    deg[0][0] = deg[0][1] = 1;
    deg[1][0] = P[0]; deg[1][1] = P[1];
    for (int i = 2; i < 31; i++) {
        deg[i][0] = deg[i - 1][0] * deg[i - 1][0];
        deg[i][1] = deg[i - 1][1] * deg[i - 1][1];
        deg[i][0] %= mod[0];
        deg[i][1] %= mod[1];
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            hs[i][j][0][0] = hs[i][j][0][1] = (s[i][j] - 'a' + 1);
    for (int st = 1; st < 31; st++){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                hs[i][j][st][0] = hs[((i+(dx*(1<<(st - 1)))%n)+2*n)%n][((j+(dy*(1<<(st - 1)))%m)+2*m)%m][st - 1][0] * deg[st][0] + hs[i][j][st - 1][0];
                hs[i][j][st][1] = hs[((i+(dx*(1<<(st - 1)))%n)+2*n)%n][((j+(dy*(1<<(st - 1)))%m)+2*m)%m][st - 1][1] * deg[st][1] + hs[i][j][st - 1][1];
                hs[i][j][st][0] %= mod[0];
                hs[i][j][st][1] %= mod[1];
            }
        }
    }
}
 
map <pair<ll, ll>, ll> mp;
vector <pair <ll, ll> > v;
void get_cnt(int k){
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            pair <ll, ll> e;
            int X = i, Y = j;
            for (int g = 0; g < 31; g++){
                if (!((1<<g) & k)) continue;
                e.first += hs[X][Y][g][0] * deg[g][0];
                e.second += hs[X][Y][g][1] * deg[g][1];
                e.first %= mod[0];
                e.second %= mod[1];
                X = ((X+(dx*(1<<g))%n)+2*n)%n;
                Y = ((Y+(dy*(1<<g))%m)+2*m)%m;
            }
            v.push_back(e);
            mp[e]++;
        }
    }
}
 
void gen(){
    for (int i = -1; i <= 1; i++){
        for (int j = -1; j <= 1; j++){
            if (!i && !j) continue;
            dx = i; dy = j;
            make_hash();
            get_cnt(k);
        }
    }
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) cin >> s[i];
    gen();
    ll ans = 0;
    sort(all(v));
    ll cnt = 0;
    if (v[1] != v[0]) ans++;
    else cnt = 1;
    for (int i = 1; i < v.size(); i++){
        if (v[i] == v[i - 1]) cnt++;
        else{
            ans += cnt * cnt;
            cnt = 1;
        }
    }
    ans += cnt * cnt;
    ll zn = n * m * 8; zn *= zn;
    ll gcd = __gcd(ans, zn);
    cout << ans/gcd << "/"<<zn/gcd;
}

Compilation message (stderr)

osmosmjerka.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("tune=native")
      | 
osmosmjerka.cpp: In function 'int32_t main()':
osmosmjerka.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 1; i < v.size(); i++){
      |                     ~~^~~~~~~~~~

• Subtask 1: 160 / 160