Submission #37315

#	Time	Username	Problem	Language	Result	Execution time	Memory
37315		wasyl	Lozinke (COCI17_lozinke)	C++11	100 / 100	103 ms	15136 KiB

lozinke

#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 (stderr)

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 / 100