Submission #250211

#	Time	Username	Problem	Language	Result	Execution time	Memory
250211		Vladikus004	Lozinke (COCI17_lozinke)	C++14	100 / 100	618 ms	13688 KiB

lozinke

#include <bits/stdc++.h>
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;

const int N = 20000 + 3, P = 31;
int n;
string s[N];
ull h[11],deg[11];

void make_hash(string &s){
    h[0] = s[0] - 'a' + 1;
    deg[0] = 1;
    for (int i = 1; i < s.size(); i++){
        h[i] = h[i - 1] * P + (s[i] - 'a' + 1);
        deg[i] = deg[i - 1] * P;
    }
}

ull get_hash(int l, int r){
    if (!l) return h[r];
    return h[r] - h[l - 1] * deg[r - l + 1];
}

map <ull, int> mp;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> s[i];
    }
    sort(s, s + n);
    reverse(s, s + n);
    int ans = 0;
    for (int i = 0; i < n; i++){
        make_hash(s[i]);
        set <ull> ms;
        for (int j = 0; j < s[i].size(); j++){
            for (int k = j; k < s[i].size(); k++){
                ms.insert(get_hash(j, k));
            }
        }
        ans += mp[get_hash(0, s[i].size() - 1)];
        for (auto u: ms){
            mp[u]++;
        }
    }
    mp.clear();
    reverse(s, s + n);
    for (int i = 0; i < n; i++){
        make_hash(s[i]);
        set <ull> ms;
        for (int j = 0; j < s[i].size(); j++){
            for (int k = j; k < s[i].size(); k++){
                ms.insert(get_hash(j, k));
            }
        }
        ans += mp[get_hash(0, s[i].size() - 1)];
        for (auto u: ms){
            mp[u]++;
        }
    }
    cout << ans;
}

Compilation message (stderr)

lozinke.cpp: In function 'void make_hash(std::__cxx11::string&)':
lozinke.cpp:18:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < s.size(); i++){
                     ~~^~~~~~~~~~
lozinke.cpp: In function 'int main()':
lozinke.cpp:48:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < s[i].size(); j++){
                         ~~^~~~~~~~~~~~~
lozinke.cpp:49:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k = j; k < s[i].size(); k++){
                             ~~^~~~~~~~~~~~~
lozinke.cpp:63:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < s[i].size(); j++){
                         ~~^~~~~~~~~~~~~
lozinke.cpp:64:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k = j; k < s[i].size(); k++){
                             ~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100