oj.uz

Submission #37314

# Submission time Handle Problem Language Result Execution time Memory
37314 2017-12-23T22:03:30 Z wasyl Lozinke (COCI17_lozinke) C++11
10 / 100
 89 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 ( int 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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2180 KB Output isn't correct
2 Correct 0 ms 2180 KB Output is correct
3 Incorrect 0 ms 2180 KB Output isn't correct
4 Correct 0 ms 2180 KB Output is correct
5 Incorrect 3 ms 2632 KB Output isn't correct
6 Incorrect 3 ms 3036 KB Output isn't correct
7 Incorrect 6 ms 3052 KB Output isn't correct
8 Incorrect 6 ms 3052 KB Output isn't correct
9 Incorrect 23 ms 5608 KB Output isn't correct
10 Incorrect 46 ms 8680 KB Output isn't correct
11 Incorrect 43 ms 8836 KB Output isn't correct
12 Incorrect 86 ms 14980 KB Output isn't correct
13 Incorrect 83 ms 15136 KB Output isn't correct
14 Incorrect 66 ms 8992 KB Output isn't correct
15 Incorrect 89 ms 15136 KB Output isn't correct
16 Incorrect 89 ms 15136 KB Output isn't correct
17 Incorrect 39 ms 5916 KB Output isn't correct
18 Incorrect 33 ms 5920 KB Output isn't correct
19 Incorrect 69 ms 8992 KB Output isn't correct
20 Incorrect 49 ms 8992 KB Output isn't correct