답안 #1011935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1011935	2024-07-01T11:17:40 Z	0npata	Lozinke (COCI17_lozinke)	C++17	70 / 100	186 ms	13604 KB

lozinke

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define vec vector

const int MX = 1e9+7;

mt19937 rng(54);

int rng_next(int mx) {
	return uniform_int_distribution<int32_t>(0, mx)(rng);
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	vec<string> a(n);

	for(int i = 0; i<n; i++) cin >> a[i];

	vec<int> pos_hash(10);
	vec<int> let_hash(26);

	for(int i = 0; i<10; i++) {
		pos_hash[i] = rng_next(MX);
	}
	for(int i = 0; i<26; i++) {
		let_hash[i] = rng_next(MX);
	}

	map<int, int> cnt;

	for(int i = 0; i<a.size(); i++) {
		set<int> subs;
		for(int j = 0; j < a[i].size(); j++) {
			int hash = 0;
			for(int k = j; k<a[i].size(); k++) {
				int pos = k-j;
				hash += pos_hash[pos] * let_hash[a[i][k]-'a'];
				hash %= MX;
				subs.insert(hash);
			}
		}

		for(int subh : subs) {
			cnt[subh] += 1;
		}
	}

	int ans = 0;
	for(int i = 0; i<n; i++) {
		int hash = 0;
		for(int j = 0; j<a[i].size(); j++) {
			hash += pos_hash[j] * let_hash[a[i][j]-'a'];
			hash %= MX;
		}
		ans += cnt[hash]-1;
	}

	cout << ans << '\n';

}

Compilation message

lozinke.cpp: In function 'int32_t main()':
lozinke.cpp:37:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i = 0; i<a.size(); i++) {
      |                 ~^~~~~~~~~
lozinke.cpp:39:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int j = 0; j < a[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~
lozinke.cpp:41:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    for(int k = j; k<a[i].size(); k++) {
      |                   ~^~~~~~~~~~~~
lozinke.cpp:57:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int j = 0; j<a[i].size(); j++) {
      |                  ~^~~~~~~~~~~~

Subtask #1

70.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	4 ms	604 KB	Output is correct
6	Correct	6 ms	604 KB	Output is correct
7	Correct	7 ms	1372 KB	Output is correct
8	Correct	12 ms	1836 KB	Output is correct
9	Correct	29 ms	2136 KB	Output is correct
10	Incorrect	77 ms	6204 KB	Output isn't correct
11	Incorrect	55 ms	3668 KB	Output isn't correct
12	Incorrect	173 ms	13604 KB	Output isn't correct
13	Correct	80 ms	2640 KB	Output is correct
14	Incorrect	133 ms	12228 KB	Output isn't correct
15	Incorrect	186 ms	13396 KB	Output isn't correct
16	Correct	89 ms	1408 KB	Output is correct
17	Correct	14 ms	1112 KB	Output is correct
18	Correct	11 ms	1112 KB	Output is correct
19	Incorrect	122 ms	7192 KB	Output isn't correct
20	Correct	40 ms	1112 KB	Output is correct