제출 #1078720

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1078720		khactrung1912	Lozinke (COCI17_lozinke)	C++14	40 / 100	1082 ms	10332 KiB

lozinke

#include<bits/stdc++.h>

using namespace std;

#define el "\n"
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define inpout(x) freopen(x".inp", "r", stdin), freopen(x".out", "w", stdout)

const int maxn = 2e4 + 5;
const ll mod = 1e9 + 7;
const ll base = 31;
const ll Mod[4] = {(ll)1e9 + 1677, (ll)1e9 + 2277, (ll)1e9 + 3577, (ll)1e9 + 3777};

int n, i, ans;
string s[maxn];
vector<ll> Hash[4][maxn];
ll pw[4][maxn];

bool check(int u, int v){
    if (s[u].size() < s[v].size())
        return false;

    for (int j = 1; j <= s[u].size() - s[v].size() + 1; j++){
        bool ok = true;

        int l = j, r = j + s[v].size() - 2;

        for (int k = 0; k < 4; k++)
            if (Hash[k][v][s[v].size() - 1] != (Hash[k][u][r] - Hash[k][u][l - 1] * pw[k][r - l + 1] + Mod[k] * Mod[k]) % Mod[k])
                ok = false;

        if (ok)
            return true;
    }
    return false;
}

signed main(){
    ios;
 //   inpout("pass");
    cin >> n;

    for (int k = 0; k < 4; k++){
        pw[k][0] = 1;
        for (i = 1; i <= 10; i++)
            pw[k][i] = pw[k][i - 1] * base;
    }

    for (i = 1; i <= n; i++){
        cin >> s[i];
        s[i] = " " + s[i];

        for (int k = 0; k < 4; k++)
            Hash[k][i].resize(s[i].size());

        for (int j = 1; j < s[i].size(); j++)
            for (int k = 0; k < 4; k++)
                Hash[k][i][j] = (Hash[k][i][j - 1] * base + s[i][j] - 'a') % Mod[k];
    }

    for (i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++)
            if (i != j && check(i, j))
                ans++;
    }

    cout << ans;
}

컴파일 시 표준 에러 (stderr) 메시지

lozinke.cpp: In function 'bool check(int, int)':
lozinke.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int j = 1; j <= s[u].size() - s[v].size() + 1; j++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp: In function 'int main()':
lozinke.cpp:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int j = 1; j < s[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~

• Subtask 1: 40 / 100