Submission #1078158

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1078158	2024-08-27T13:26:17 Z	ntnq	Lozinke (COCI17_lozinke)	C++17	5 / 100	23 ms	1228 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	860 KB	Output isn't correct
2	Incorrect	1 ms	860 KB	Output isn't correct
3	Incorrect	1 ms	860 KB	Output isn't correct
4	Incorrect	2 ms	1116 KB	Output isn't correct
5	Incorrect	6 ms	1116 KB	Output isn't correct
6	Incorrect	11 ms	1228 KB	Output isn't correct
7	Incorrect	23 ms	1116 KB	Output isn't correct
8	Correct	17 ms	1116 KB	Output is correct
9	Incorrect	1 ms	860 KB	Output isn't correct
10	Incorrect	1 ms	860 KB	Output isn't correct
11	Incorrect	1 ms	860 KB	Output isn't correct
12	Incorrect	1 ms	860 KB	Output isn't correct
13	Incorrect	1 ms	860 KB	Output isn't correct
14	Incorrect	1 ms	860 KB	Output isn't correct
15	Incorrect	2 ms	860 KB	Output isn't correct
16	Incorrect	1 ms	860 KB	Output isn't correct
17	Incorrect	1 ms	860 KB	Output isn't correct
18	Incorrect	1 ms	860 KB	Output isn't correct
19	Incorrect	2 ms	860 KB	Output isn't correct
20	Incorrect	1 ms	860 KB	Output isn't correct