oj.uz

답안 #1078719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1078719 2024-08-28T05:03:16 Z khactrung1912 Lozinke (COCI17_lozinke) C++14
0 / 100
 4 ms 3160 KB 
#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;
}

Compilation message

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++)
      |                         ~~^~~~~~~~~~~~~
lozinke.cpp:11:26: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define inpout(x) freopen(x".inp", "r", stdin), freopen(x".out", "w", stdout)
      |                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:44:5: note: in expansion of macro 'inpout'
   44 |     inpout("pass");
      |     ^~~~~~
lozinke.cpp:11:56: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define inpout(x) freopen(x".inp", "r", stdin), freopen(x".out", "w", stdout)
      |                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:44:5: note: in expansion of macro 'inpout'
   44 |     inpout("pass");
      |     ^~~~~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2912 KB Output isn't correct
2 Incorrect 3 ms 2908 KB Output isn't correct
3 Incorrect 2 ms 2908 KB Output isn't correct
4 Incorrect 2 ms 2908 KB Output isn't correct
5 Incorrect 4 ms 3040 KB Output isn't correct
6 Incorrect 3 ms 2908 KB Output isn't correct
7 Incorrect 3 ms 2904 KB Output isn't correct
8 Incorrect 3 ms 2908 KB Output isn't correct
9 Incorrect 2 ms 2908 KB Output isn't correct
10 Incorrect 3 ms 2908 KB Output isn't correct
11 Incorrect 3 ms 2908 KB Output isn't correct
12 Incorrect 4 ms 2908 KB Output isn't correct
13 Incorrect 3 ms 2908 KB Output isn't correct
14 Incorrect 3 ms 2908 KB Output isn't correct
15 Incorrect 4 ms 2908 KB Output isn't correct
16 Incorrect 3 ms 2908 KB Output isn't correct
17 Incorrect 3 ms 2908 KB Output isn't correct
18 Incorrect 2 ms 2908 KB Output isn't correct
19 Incorrect 4 ms 3160 KB Output isn't correct
20 Incorrect 4 ms 2908 KB Output isn't correct