oj.uz

Submission #37312

# Submission time Handle Problem Language Result Execution time Memory
37312 2017-12-23T21:58:47 Z wasyl Lozinke (COCI17_lozinke) C++11
85 / 100
 89 ms 8992 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 int mod = 1e9 + 7;

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

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

int count ( string& s )
{
	int hasz = 0;
	for ( char c : s )
		hasz = ( (ll)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
85.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 2372 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 3 ms 2668 KB Output is correct
8 Correct 6 ms 2668 KB Output is correct
9 Correct 26 ms 4072 KB Output is correct
10 Incorrect 39 ms 5608 KB Output isn't correct
11 Correct 36 ms 5764 KB Output is correct
12 Correct 83 ms 8836 KB Output is correct
13 Correct 76 ms 8992 KB Output is correct
14 Incorrect 69 ms 5920 KB Output isn't correct
15 Incorrect 89 ms 8992 KB Output isn't correct
16 Correct 89 ms 8992 KB Output is correct
17 Correct 33 ms 4380 KB Output is correct
18 Correct 33 ms 4384 KB Output is correct
19 Correct 66 ms 5920 KB Output is correct
20 Correct 49 ms 5920 KB Output is correct