oj.uz

답안 #416126

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
416126 2021-06-02T02:55:57 Z SirCovidThe19th Osmosmjerka (COCI17_osmosmjerka) C++14
100 / 160
 1439 ms 33728 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
const ll p1 = 1663, p2 = 5953, mod = 1e9+7;
 
//left, right, up, down, up left, up right, down right, down left
int n, m, k; string grid[500];
int di[8] = {0, 0, -1, 1, -1, -1, 1, 1}, dj[8] = {-1, 1, 0, 0, -1, 1, 1, -1};
ll pow1 = 1, pow2 = 1; map<pair<ll, ll>, int> eq;
 
bool in1(int i, int j) { return i >= 0 and i < n and j >= 0 and j < m; }
bool in2(int i, int j, int d) { return in1(i-(k-1)*di[d], j-(k-1)*dj[d]); }
void solve(int ti, int tj, int move, int d){
    for (; in1(ti, tj); ti += di[move], tj += dj[move]){
        ll hash1 = 0, hash2 = 0;
        for (int i = ti, j = tj, cnt = 1; cnt <= k or in2(i, j, d); i += di[d], j += dj[d], cnt++){
            int curr = grid[(i+500*n)%n][(j+500*m)%m]-'a'+1;
            hash1 = ((hash1*p1)+(curr))%mod; hash2 = ((hash2*p2)+(curr))%mod;
            if (cnt > k){
                hash1 = (hash1-(pow1*(grid[i-k*di[d]][j-k*dj[d]]-'a'+1)%mod)+mod)%mod;
                hash2 = (hash2-(pow2*(grid[i-k*di[d]][j-k*dj[d]]-'a'+1)%mod)+mod)%mod;
            }
            if (cnt >= k)
                eq[{hash1, hash2}]++;
        }
    }
}
 
int main() {
 
    cin >> n >> m >> k; k = min(k, max(n, m)+1);
    for (int i = 0; i < n; i++) cin >> grid[i];
    for (int i = 0; i < k; i++) pow1 = (pow1*p1)%mod, pow2 = (pow2*p2)%mod;
 
    solve(0, 0, 1, 7); solve(0, 0, 1, 6); solve(n-1, 0, 1, 4); solve(n-1, 0, 1, 5);
    solve(n-2, 0, 2, 5); solve(n-2, m-1, 2, 4); solve(1, 0, 3, 6); solve(1, m-1, 3, 7);
    solve(0, 0, 1, 3); solve(n-1, 0, 1, 2); solve(0, 0, 3, 1); solve(0, m-1, 3, 0);
 
    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;
}

Subtask #1
100.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Incorrect 16 ms 1740 KB Output isn't correct
7 Incorrect 217 ms 8656 KB Output isn't correct
8 Incorrect 1439 ms 33728 KB Output isn't correct