Submission #1497330


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
//#define int long long

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll mod = 1e9 + 7;
const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;
const ull B = 1e9 + 7;

int n, m;
vector<string> s(255);
vector<vector<ull>> hs1(255, vector<ull> (255, 0)), hs2(255, vector<ull> (255, 0));
ull power[255];

void constract(vector<string>& s) {
    rep(i, n) {
        ull tmp = 0;
        rep(j, m) {
            tmp = tmp * B + s[i][j];
            hs1[i][j] = tmp;
        }
        tmp = 0;
        rrep2(j, m - 1, -1) {
            tmp = tmp * B + s[i][j];
            hs2[i][j] = tmp;
        }
    }
}

bool match(int top, int btm, int s, int t) {
    ull tmp1, tmp2;
    if (s == 0) tmp1 = hs1[top][t];
    else tmp1 = hs1[top][t] - hs1[top][s - 1] * power[t - s + 1];
    if (t == m - 1) tmp2 = hs2[btm][s];
    else tmp2 = hs2[btm][s] - hs2[btm][t + 1] * power[t - s + 1];
    return tmp1 == tmp2 ? true : false;
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    power[0] = 1;
    rep2(i, 1, m + 1) power[i] = B * power[i - 1];
    rep(i, n)  cin >> s[i];
    constract(s);
    ll ans = 0LL;
    rep2(i, 1, n) {
        rep(j, m - 1) {
            int l = j - 1, r = j + 1;
            int t = i - 1, b = i;
            while (0 <= l && r < m) {
                if (!match(t, b, l, r)) break;
                ans++;
                l--;
                r++;
            }
            if (r - l != 2) {
                l++; r--;
                t--; b++;
                while (0 <= t && b < n) {
                    if (!match(t, b, l, r)) {
                        while (l < r && !match(t, b, l, r)) {
                            l++;
                            r--;
                        }
                        if (l == r) break;
                    }
                    ans += r - j;   
                    t--;
                    b++;
                }
            }
            l = j; r = j + 1;
            t = i - 1; b = i;
            while (0 <= l && r < m) {
                if (!match(t, b, l, r)) break;
                ans++;
                l--;
                r++;
            }
            if (r - l != 1) {
                l++; r--;
                t--; b++;
                while (0 <= t && b < n) {
                    if (!match(t, b, l, r)) {
                        while (l < r && !match(t, b, l, r)) {
                            l++;
                            r--;
                        }
                        if (r <= l) break;
                    }
                    ans += r - j;
                    t--;
                    b++;
                }
            }
        }
    }
    cout << ans << endl;
}

Submission Info

Submission Time
Task H - 模様替え
User roto_37
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3620 Byte
Status WA
Exec Time 113 ms
Memory 1408 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 0 / 15 0 / 30 0 / 55
Status
AC × 2
AC × 6
WA × 16
AC × 6
WA × 31
AC × 6
WA × 46
Set Name Test Cases
Sample subtask0-sample-01.txt, subtask0-sample-02.txt
Subtask1 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt
Subtask2 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt
Subtask3 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt
Case Name Status Exec Time Memory
subtask0-sample-01.txt AC 2 ms 1280 KB
subtask0-sample-02.txt AC 2 ms 1280 KB
subtask1-01.txt AC 2 ms 1280 KB
subtask1-02.txt WA 2 ms 1280 KB
subtask1-03.txt WA 2 ms 1280 KB
subtask1-04.txt AC 2 ms 1280 KB
subtask1-05.txt WA 2 ms 1280 KB
subtask1-06.txt WA 2 ms 1280 KB
subtask1-07.txt AC 2 ms 1280 KB
subtask1-08.txt WA 2 ms 1280 KB
subtask1-09.txt WA 2 ms 1280 KB
subtask1-10.txt WA 2 ms 1280 KB
subtask1-11.txt WA 2 ms 1280 KB
subtask1-12.txt WA 2 ms 1280 KB
subtask1-13.txt WA 2 ms 1280 KB
subtask1-14.txt WA 2 ms 1280 KB
subtask1-15.txt WA 2 ms 1280 KB
subtask1-16.txt AC 2 ms 1280 KB
subtask1-17.txt WA 2 ms 1280 KB
subtask1-18.txt WA 2 ms 1280 KB
subtask1-19.txt WA 2 ms 1280 KB
subtask1-20.txt WA 2 ms 1280 KB
subtask2-01.txt WA 2 ms 1280 KB
subtask2-02.txt WA 2 ms 1280 KB
subtask2-03.txt WA 2 ms 1280 KB
subtask2-04.txt WA 2 ms 1280 KB
subtask2-05.txt WA 2 ms 1280 KB
subtask2-06.txt WA 9 ms 1280 KB
subtask2-07.txt WA 2 ms 1280 KB
subtask2-08.txt WA 2 ms 1280 KB
subtask2-09.txt WA 2 ms 1280 KB
subtask2-10.txt WA 8 ms 1280 KB
subtask2-11.txt WA 7 ms 1280 KB
subtask2-12.txt WA 2 ms 1280 KB
subtask2-13.txt WA 8 ms 1280 KB
subtask2-14.txt WA 2 ms 1280 KB
subtask2-15.txt WA 2 ms 1280 KB
subtask3-01.txt WA 2 ms 1280 KB
subtask3-02.txt WA 2 ms 1280 KB
subtask3-03.txt WA 2 ms 1280 KB
subtask3-04.txt WA 2 ms 1280 KB
subtask3-05.txt WA 2 ms 1280 KB
subtask3-06.txt WA 112 ms 1408 KB
subtask3-07.txt WA 17 ms 1408 KB
subtask3-08.txt WA 3 ms 1408 KB
subtask3-09.txt WA 3 ms 1408 KB
subtask3-10.txt WA 3 ms 1408 KB
subtask3-11.txt WA 3 ms 1408 KB
subtask3-12.txt WA 3 ms 1408 KB
subtask3-13.txt WA 113 ms 1408 KB
subtask3-14.txt WA 3 ms 1408 KB
subtask3-15.txt WA 3 ms 1408 KB