Submission #165732

#	Time	Username	Problem	Language	Result	Execution time	Memory
165732		Sensei	Lozinke (COCI17_lozinke)	C++17	50 / 100	1088 ms	3448 KiB

lozinke

    #include <bits/stdc++.h>
     
    using namespace std;
     
    const long long P = 53;
    const long long MOD = 1e9 + 7;
     
    const int MAXN = 2e4;
     
    long long add (long long x, long long y) {
    	return ((x % MOD) + (y % MOD)) % MOD;
    }
     
    long long mul (long long x, long long y) {
    	return ((x % MOD) * (y % MOD)) % MOD;
    }
     
    map<long long, set<int> > m;
    string st[MAXN + 7];
     
    int main () {
    	int N;
    	cin >> N;
     
    	for (int i = 1; i <= N; i++) {
    		cin >> st[i];
    	}
     
    	for (int i = 1; i <= N; i++) {
    		long long hash = 0;
     
    		for (int j = 0; j < st[i].size(); j++) {
    			hash = mul(hash, P);
    			hash = add(hash, st[i][j] - 'a' + 1);
    		}
     
    		m[hash].insert(i);
    	}
     
    	long long ans = 0;
     
    	for (int i = 1; i <= N; i++) {
    		vector<bool> s(N + 1, false);
     
    		for (int ss = 0; ss < st[i].size(); ss++) {
    			long long hash = 0;
     
    			for (int j = ss; j < st[i].size(); j++) {
    				if (ss == 0 && j + 1 == st[i].size()) {
    					break;
    				}
     
    				hash = mul(hash, P);
    				hash = add(hash, st[i][j] - 'a' + 1);
     
    				if (m.find(hash) != m.end()) {
    					for (int id : m[hash]) {
    						if (id != i) {
    							s[id] = true;
    						}
    					}
    				}
    			}
    		}

    		for (int j = 1; j <= N; j++) {
    			if (i != j) {
    				ans += s[j];
    			}
    		}
    	}
     
    	long long ans2 = 0;
     
    	for (int i = 1; i <= N; i++) {
    		long long hash = 0;
     
    		for (int j = 0; j < st[i].size(); j++) {
    			hash = mul(hash, P);
    			hash = add(hash, st[i][j] - 'a' + 1);
    		}
     
    		ans2 += m[hash].size() - 1;
    	}
     
    	ans += ans2;
     
    	cout << ans << "\n";
     
    	return 0;
    }

Compilation message (stderr)

lozinke.cpp: In function 'int main()':
lozinke.cpp:32:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < st[i].size(); j++) {
                       ~~^~~~~~~~~~~~~~
lozinke.cpp:45:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int ss = 0; ss < st[i].size(); ss++) {
                        ~~~^~~~~~~~~~~~~~
lozinke.cpp:48:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for (int j = ss; j < st[i].size(); j++) {
                         ~~^~~~~~~~~~~~~~
lozinke.cpp:49:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (ss == 0 && j + 1 == st[i].size()) {
                        ~~~~~~^~~~~~~~~~~~~~~
lozinke.cpp:78:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < st[i].size(); j++) {
                       ~~^~~~~~~~~~~~~~

• Subtask 1: 50 / 100