Submission #34856

#	Time	Username	Problem	Language	Result	Execution time	Memory
34856		szawinis	Lozinke (COCI17_lozinke)	C++14	90 / 100	1000 ms	15656 KiB

lozinke

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e4+1;
const ll MOD = 1e9+7;

int n, ans;
string s[N];
pair<ll, ll> h[N];
map<pair<ll, ll>, int> mp;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> s[i];
		h[i].first = h[i].second = s[i][0] - 'a' + 1;
		for(int j = 1; j < s[i].length(); j++) {
			h[i].first = (h[i].first * 31 + s[i][j] - 'a' + 1) % MOD;
			h[i].second = (h[i].second * 37 + s[i][j] - 'a' + 1) % MOD;
		}
	}
	for(int i = 0; i < n; i++) {
		set<pair<ll, ll> > ls;
		for(int x = 0; x < s[i].length(); x++) {
			pair<ll, ll> currh = {s[i][x]-'a' + 1, s[i][x]-'a' + 1};
			ls.insert(currh);
			for(int y = x+1; y < s[i].length(); y++) {
				currh.first = (currh.first * 31 + s[i][y] - 'a' + 1) % MOD;
				currh.second = (currh.second * 37 + s[i][y] - 'a' + 1) % MOD;
				ls.insert(currh);
			}
		}
		for(auto p: ls) ans += mp[p];
		++mp[h[i]];
	}
	mp.clear();
	for(int i = n-1; i >= 0; i--) {
		set<pair<ll, ll> > ls;
		for(int x = 0; x < s[i].length(); x++) {
			pair<ll, ll> currh = {s[i][x]-'a' + 1, s[i][x]-'a' + 1};
			ls.insert(currh);
			for(int y = x+1; y < s[i].length(); y++) {
				currh.first = (currh.first * 31 + s[i][y] - 'a' + 1) % MOD;
				currh.second = (currh.second * 37 + s[i][y] - 'a' + 1) % MOD;
				ls.insert(currh);
			}
		}
		for(auto p: ls) ans += mp[p];
		++mp[h[i]];
	}
	cout << ans;
}

Compilation message (stderr)

lozinke.cpp: In function 'int main()':
lozinke.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 1; j < s[i].length(); j++) {
                    ^
lozinke.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int x = 0; x < s[i].length(); x++) {
                    ^
lozinke.cpp:28:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int y = x+1; y < s[i].length(); y++) {
                       ^
lozinke.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int x = 0; x < s[i].length(); x++) {
                    ^
lozinke.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int y = x+1; y < s[i].length(); y++) {
                       ^

• Subtask 1: 90 / 100