Submission #165734

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
165734	2019-11-28T12:16:52 Z	Sensei	Lozinke (COCI17_lozinke)	C++17	40 / 100	1000 ms	11896 KB

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;
}

string st[MAXN + 7];
long long fullhash[MAXN + 7];
vector<long long> subhashes[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++) {
		for (int ss = 0; ss < st[i].size(); ss++) {
			long long hash = 0;

			for (int j = ss; j < st[i].size(); j++) {
				hash = mul(hash, P);
				hash = add(hash, st[i][j] - 'a' + 1);

				subhashes[i].push_back(hash);
				if (ss == 0 && j + 1 == st[i].size()) {
					fullhash[i] = hash;
				}
			}
		}

		sort(subhashes[i].begin(), subhashes[i].end());
	}

	long long ans = 0;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i != j && binary_search(subhashes[i].begin(), subhashes[i].end(), fullhash[j]) == true) {
				ans++;
			}
		}
	}

	cout << ans << "\n";

	return 0;
}

Compilation message

lozinke.cpp: In function 'int main()':
lozinke.cpp:31:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int ss = 0; ss < st[i].size(); ss++) {
                    ~~~^~~~~~~~~~~~~~
lozinke.cpp:34:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = ss; j < st[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~
lozinke.cpp:39:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (ss == 0 && j + 1 == st[i].size()) {
                    ~~~~~~^~~~~~~~~~~~~~~

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1400 KB	Output is correct
2	Correct	3 ms	1400 KB	Output is correct
3	Correct	3 ms	1400 KB	Output is correct
4	Correct	7 ms	1400 KB	Output is correct
5	Correct	31 ms	1656 KB	Output is correct
6	Correct	55 ms	1912 KB	Output is correct
7	Correct	90 ms	2040 KB	Output is correct
8	Correct	96 ms	2268 KB	Output is correct
9	Execution timed out	1076 ms	4216 KB	Time limit exceeded
10	Execution timed out	1067 ms	5240 KB	Time limit exceeded
11	Execution timed out	1056 ms	5368 KB	Time limit exceeded
12	Execution timed out	1070 ms	8312 KB	Time limit exceeded
13	Execution timed out	1056 ms	9928 KB	Time limit exceeded
14	Execution timed out	1074 ms	6520 KB	Time limit exceeded
15	Execution timed out	1049 ms	9080 KB	Time limit exceeded
16	Execution timed out	1086 ms	11896 KB	Time limit exceeded
17	Execution timed out	1075 ms	11896 KB	Time limit exceeded
18	Execution timed out	1041 ms	9976 KB	Time limit exceeded
19	Execution timed out	1072 ms	7744 KB	Time limit exceeded
20	Execution timed out	1050 ms	7800 KB	Time limit exceeded