oj.uz

Submission #37313

# Submission time Handle Problem Language Result Execution time Memory
37313 2017-12-23T22:01:56 Z wasyl Lozinke (COCI17_lozinke) C++11
10 / 100
 96 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< int > 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 0 ms 2632 KB Output isn't correct
6 Incorrect 6 ms 3036 KB Output isn't correct
7 Incorrect 6 ms 3052 KB Output isn't correct
8 Incorrect 3 ms 3052 KB Output isn't correct
9 Incorrect 26 ms 5608 KB Output isn't correct
10 Incorrect 53 ms 8680 KB Output isn't correct
11 Incorrect 46 ms 8836 KB Output isn't correct
12 Incorrect 83 ms 14980 KB Output isn't correct
13 Incorrect 79 ms 15136 KB Output isn't correct
14 Incorrect 63 ms 8992 KB Output isn't correct
15 Incorrect 96 ms 15136 KB Output isn't correct
16 Incorrect 89 ms 15136 KB Output isn't correct
17 Incorrect 33 ms 5916 KB Output isn't correct
18 Incorrect 29 ms 5920 KB Output isn't correct
19 Incorrect 73 ms 8992 KB Output isn't correct
20 Incorrect 53 ms 8992 KB Output isn't correct