oj.uz

답안 #165734

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
165734 2019-11-28T12:16:52 Z Sensei Lozinke (COCI17_lozinke) C++17
40 / 100
 1000 ms 11896 KB 
#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

# 결과 실행 시간 메모리 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