oj.uz

Submission #826503

# Submission time Handle Problem Language Result Execution time Memory
826503 2023-08-15T16:06:09 Z QwertyPi Necklace (Subtask 1-3) (BOI19_necklace1) C++14
9 / 85
 1500 ms 340 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct answer{
	int a, x, y;
};

const int P = 1e9 + 7, A = 13895;
const int N = 3e4 + 11;
int norm(int x){
	return (x % P + P) % P;
}

int h_s[N], h_t[N], pw[N];

int hash_s(int i, int l){
	return norm(h_s[i + l] - h_s[i] * pw[l]);
}

int hash_t(int i, int l){
	return norm(h_t[i + l] - h_t[i] * pw[l]);
}

bool are_equal(int l, int i, int j){
	for(int k = 0; k < l; k++){
		if(hash_s(i, l) == norm(hash_t(j + k, l - k) * pw[k] + hash_t(j, k))){
			return true;
		}
	}
	return false;
}

int n, m; string s, t;
bool try_length(int l){
	for(int i = 0; i <= n - l; i++){
		for(int j = 0; j <= m - l; j++){
			bool ok = are_equal(l, i, j);
			if(ok) return true;
		}
	}
	return false;
}

answer construct_length(int l){
	for(int i = 0; i <= n - l; i++){
		for(int j = 0; j <= m - l; j++){
			bool ok = are_equal(l, i, j);
			if(ok) return {l, i, j};
		}
	}
	assert(1 == 0);
}

answer query(const string& s, const string& t){
	::s = s, ::t = t, n = s.size(), m = t.size();
	h_s[0] = 0; for(int i = 0; i < n; i++) h_s[i + 1] = (h_s[i] * A + s[i] - 'a') % P;
	h_t[0] = 0; for(int i = 0; i < m; i++) h_t[i + 1] = (h_t[i] * A + t[i] - 'a') % P;
	pw[0] = 1; for(int i = 0; i < max(n, m); i++) pw[i + 1] = pw[i] * A % P;

	int lo = 0, hi = min(n, m);
	while(lo != hi){
		int mid = (lo + hi + 1) / 2;
		if(try_length(mid)){
			lo = mid;
		}else{
			hi = mid - 1;
		}
	}

	answer ans = construct_length(lo);
	return ans;
}

int32_t main(){
	string s, t; cin >> s >> t;
	answer a1 = query(s, t);
	reverse(t.begin(), t.end());
	answer a2 = query(s, t); a2.y = t.size() - (a2.y + a2.a);

	answer ans; ans.a = -1;
	if(a1.a > ans.a) ans = a1;
	if(a2.a > ans.a) ans = a2;
	cout << ans.a << endl;
	cout << ans.x << ' ' << ans.y << endl; 
}

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Partially correct 3 ms 212 KB Output is partially correct
3 Correct 8 ms 212 KB Output is correct
4 Partially correct 9 ms 212 KB Output is partially correct
5 Correct 9 ms 320 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Partially correct 3 ms 212 KB Output is partially correct
3 Correct 8 ms 212 KB Output is correct
4 Partially correct 9 ms 212 KB Output is partially correct
5 Correct 9 ms 320 KB Output is correct
6 Correct 81 ms 308 KB Output is correct
7 Partially correct 230 ms 308 KB Output is partially correct
8 Correct 791 ms 304 KB Output is correct
9 Partially correct 734 ms 308 KB Output is partially correct
10 Partially correct 737 ms 308 KB Output is partially correct
11 Partially correct 613 ms 308 KB Output is partially correct
12 Correct 889 ms 304 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Partially correct 3 ms 212 KB Output is partially correct
3 Correct 8 ms 212 KB Output is correct
4 Partially correct 9 ms 212 KB Output is partially correct
5 Correct 9 ms 320 KB Output is correct
6 Correct 81 ms 308 KB Output is correct
7 Partially correct 230 ms 308 KB Output is partially correct
8 Correct 791 ms 304 KB Output is correct
9 Partially correct 734 ms 308 KB Output is partially correct
10 Partially correct 737 ms 308 KB Output is partially correct
11 Partially correct 613 ms 308 KB Output is partially correct
12 Correct 889 ms 304 KB Output is correct
13 Execution timed out 1571 ms 340 KB Time limit exceeded
14 Halted 0 ms 0 KB -