Submission #1078724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078724		khactrung1912	Lozinke (COCI17_lozinke)	C++14	5 / 100	23 ms	1184 KiB

lozinke

// CAU DUA DU DAU
#include <bits/stdc++.h>
using namespace std;

#define uf(i, a, b) for (int i = (a); i <= (b); i++)
#define df(i, a, b) for (int i = (a); i >= (b); i--)
#define rep(i, n) for (int i = 1; i <= (n); i++)
#define ll long long
#define sz(k) (int)k.size()
#define task "PASS"

template <class T> 
	bool maximize(T &a, const T &b){
		if (a < b){
			a = b; 
			return 1;
		} else return 0;
	};
template <class T> 
	bool minimize(T &a, const T &b){
		if (a > b){
			a = b; 
			return 1;
		} else return 0;
	};

const int maxn = 2e4+10;
const ll MOD = 1e9+7;

int n, base = 311;
string s[maxn];
ll hashS[maxn][11], h[maxn];

bool cmp(string a, string b){
	return sz(a) < sz(b);
}

ll get(int id, int l, int r){
	return (hashS[id][r] - hashS[id][l-1] * h[r-l+1] + MOD * MOD) % MOD;
}

void sub1(){
	sort(s+1, s+1+n, cmp);
	h[0] = 1;
	rep(i, 11) h[i] = (h[i-1] * base) % MOD;
	rep(i, n){
		s[i] = ' ' + s[i];
		hashS[i][0] = 0;
		for (int j = 1; j < sz(s[i]); j++) hashS[i][j] = (hashS[i][j-1] * base + s[i][j]) % MOD;
	}
	ll cnt = 0;
	rep(i, n){
		for (int j = i-1; j >= 1; j--){
			for (int l = 1; l <= sz(s[i]) - sz(s[j]) + 1; l++){
				int r = l + sz(s[j]) - 2;
				if (get(i, l, r) == hashS[j][sz(s[j])-1]) cnt++;
			}
			if (sz(s[i]) == sz(s[j]) && hashS[i][sz(s[i])-1] == hashS[j][sz(s[j])-1]) cnt++;
		}
	}
	cout << cnt;
}

void solve(){
	cin >> n;
	rep(i, n) cin >> s[i];
	if (n <= (int)2e3) sub1();
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int numTest = 1;
//	cin >> numTest;
	while (numTest--) solve();
	return 0;
}

• Subtask 1: 5 / 100