oj.uz

Submission #444201

# Submission time Handle Problem Language Result Execution time Memory
444201 2021-07-13T10:44:29 Z BeanZ Lozinke (COCI17_lozinke) C++14
15 / 100
 210 ms 15988 KB 
// I_Love_LPL 1y0m3d
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1e5 + 5;
long long mod = 1e9 + 7;
const int lim = 4e5 + 5;
const int lg = 20;
const int base = 311;
const long double eps = 1e-6;
string s[N];
ll h[N], p[N];
map<ll, ll> mem;
ll get(ll l, ll r){
    return (h[r] - h[l - 1] * p[r - l + 1] + mod * mod) % mod;
}
bool cmp(string x, string y){
    return x.length() < y.length();
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> s[i];
    }
    sort(s + 1, s + n + 1, cmp);
    p[0] = 1;
    ll ans = 0;
    for (int i = 1; i <= 10; i++) p[i] = p[i - 1] * base % mod;
    for (int i = 1; i <= n; i++){
        ll x = s[i].length();
        for (int j = 1; j <= x; j++){
            h[j] = (h[j - 1] * base + (s[i][j - 1] - 'a' + 1)) % mod;
        }
        for (int j = 1; j <= x; j++){
            for (int k = j; k <= x; k++){
                if (j == 1 && k == x) continue;
                ans = ans + mem[get(j, k)];
            }
        }
        mem[h[x]]++;
    }
    for (auto j : mem){
        ans = ans + j.second * (j.second - 1);
    }
    cout << ans;
}
/*
Ans:

Out:
*/

Compilation message

lozinke.cpp: In function 'int main()':
lozinke.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3404 KB Output isn't correct
2 Incorrect 2 ms 3404 KB Output isn't correct
3 Incorrect 2 ms 3404 KB Output isn't correct
4 Incorrect 3 ms 3404 KB Output isn't correct
5 Incorrect 5 ms 3660 KB Output isn't correct
6 Incorrect 6 ms 3652 KB Output isn't correct
7 Incorrect 12 ms 4260 KB Output isn't correct
8 Correct 15 ms 4940 KB Output is correct
9 Incorrect 27 ms 4856 KB Output isn't correct
10 Correct 73 ms 8848 KB Output is correct
11 Incorrect 46 ms 6084 KB Output isn't correct
12 Incorrect 203 ms 15988 KB Output isn't correct
13 Incorrect 67 ms 4732 KB Output isn't correct
14 Incorrect 152 ms 14516 KB Output isn't correct
15 Incorrect 210 ms 15768 KB Output isn't correct
16 Incorrect 62 ms 3564 KB Output isn't correct
17 Correct 24 ms 3460 KB Output is correct
18 Incorrect 20 ms 3448 KB Output isn't correct
19 Incorrect 102 ms 9444 KB Output isn't correct
20 Incorrect 28 ms 3492 KB Output isn't correct