oj.uz

Submission #1078724

# Submission time Handle Problem Language Result Execution time Memory
1078724 2024-08-28T05:09:19 Z khactrung1912 Lozinke (COCI17_lozinke) C++14
5 / 100
 23 ms 1184 KB 
// 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 1 ms 1116 KB Output isn't correct
5 Incorrect 6 ms 1184 KB Output isn't correct
6 Incorrect 11 ms 1116 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 2 ms 860 KB Output isn't correct
12 Incorrect 1 ms 860 KB Output isn't correct
13 Incorrect 2 ms 948 KB Output isn't correct
14 Incorrect 2 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 2 ms 860 KB Output isn't correct
19 Incorrect 1 ms 860 KB Output isn't correct
20 Incorrect 2 ms 860 KB Output isn't correct