oj.uz

Submission #444200

# Submission time Handle Problem Language Result Execution time Memory
444200 2021-07-13T10:43:55 Z BeanZ Lozinke (COCI17_lozinke) C++14
15 / 100
 215 ms 14276 KB 
// I_Love_LPL 1y0m3d
#include <bits/stdc++.h>
using namespace std;
#define ll int
#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 3452 KB Output isn't correct
3 Incorrect 2 ms 3404 KB Output isn't correct
4 Incorrect 2 ms 3404 KB Output isn't correct
5 Incorrect 6 ms 3788 KB Output isn't correct
6 Incorrect 8 ms 3916 KB Output isn't correct
7 Incorrect 10 ms 4236 KB Output isn't correct
8 Correct 15 ms 4680 KB Output is correct
9 Incorrect 39 ms 5832 KB Output isn't correct
10 Incorrect 78 ms 8368 KB Output isn't correct
11 Incorrect 63 ms 7476 KB Output isn't correct
12 Correct 206 ms 14276 KB Output is correct
13 Incorrect 107 ms 7704 KB Output isn't correct
14 Incorrect 153 ms 13024 KB Output isn't correct
15 Incorrect 215 ms 14148 KB Output isn't correct
16 Incorrect 92 ms 4124 KB Output isn't correct
17 Correct 27 ms 3680 KB Output is correct
18 Incorrect 21 ms 3620 KB Output isn't correct
19 Incorrect 124 ms 9736 KB Output isn't correct
20 Incorrect 45 ms 3908 KB Output isn't correct