oj.uz

Submission #37315

# Submission time Handle Problem Language Result Execution time Memory
37315 2017-12-23T22:04:22 Z wasyl Lozinke (COCI17_lozinke) C++11
100 / 100
 103 ms 15136 KB 
#include <vector>
#include <iostream>
#include <algorithm>
#define d(...) __VA_ARGS__
#define all(x) (x).begin(), (x).end()
#define eb(...) emplace_back(__VA_ARGS__)
using namespace std;using ll=long long;
template<class t>using V = vector< t >;

const int p = 29;
const ll mod = (ll)1e15 + 37;

int n;
V< ll > hasze;
V< string > pass;

void parse ( string& s )
{
	V< ll > tmp;
	for ( int i = 0; i < s.size(); ++i )
	{
		ll hasz = 0;
		for ( int k = i; k < s.size(); ++k )
		{
			hasz = ( hasz * p + s[k] - 'a' + 1 ) % mod;
			tmp.eb( hasz );
		}
	}
	sort( all( tmp ) );
	tmp.resize( unique( all( tmp ) ) - tmp.begin() );
	for ( ll h : tmp )
		hasze.eb( h );
}

int count ( string& s )
{
	ll hasz = 0;
	for ( char c : s )
		hasz = ( hasz * p + c - 'a' + 1 ) % mod;
	return upper_bound( all( hasze ), hasz ) - lower_bound( all( hasze ), hasz );
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	pass.resize( n );

	for ( auto& i : pass )
		cin >> i;
	for ( auto& i : pass )
		parse( i );
	
	sort( all( hasze ) );
	hasze.eb( mod );
	
	int res = 0;
	for ( auto& i : pass )
		res += count( i ) - 1;
	cout << res << '\n';
}

Compilation message

lozinke.cpp: In function 'void parse(std::__cxx11::string&)':
lozinke.cpp:20:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for ( int i = 0; i < s.size(); ++i )
                     ^
lozinke.cpp:23:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for ( int k = i; k < s.size(); ++k )
                      ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2180 KB Output is correct
2 Correct 0 ms 2180 KB Output is correct
3 Correct 0 ms 2180 KB Output is correct
4 Correct 0 ms 2180 KB Output is correct
5 Correct 3 ms 2632 KB Output is correct
6 Correct 3 ms 3036 KB Output is correct
7 Correct 6 ms 3052 KB Output is correct
8 Correct 9 ms 3052 KB Output is correct
9 Correct 29 ms 5608 KB Output is correct
10 Correct 46 ms 8680 KB Output is correct
11 Correct 46 ms 8836 KB Output is correct
12 Correct 93 ms 14980 KB Output is correct
13 Correct 86 ms 15136 KB Output is correct
14 Correct 73 ms 8992 KB Output is correct
15 Correct 103 ms 15136 KB Output is correct
16 Correct 96 ms 15136 KB Output is correct
17 Correct 49 ms 5916 KB Output is correct
18 Correct 33 ms 5920 KB Output is correct
19 Correct 76 ms 8992 KB Output is correct
20 Correct 53 ms 8992 KB Output is correct