oj.uz

Submission #867047

# Submission time Handle Problem Language Result Execution time Memory
867047 2023-10-27T15:26:10 Z serifefedartar Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 176 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll P = 31;
const ll LOGN = 20; 
const ll MAXN = 1e5 + 5;

int ans[3], n, m;
int p1[MAXN], p2[MAXN];
void compute(string s, int p_array[]) {
	int q = s.length();
	p_array[0] = 0;
	for (int i = 1; i < q; i++) {
		int j = p_array[i-1];
		while (j && s[i] != s[j])
			j = p_array[j-1];
		if (s[i] == s[j])
			j++;
		p_array[i] = j;
	}
}

void solve(string s, string t, bool rev) {
	string t_rev = t;
	reverse(t_rev.begin(), t_rev.end());
	for (int i = 0; i < n; i++) {
		string l_up = s.substr(0, i), r_up = s.substr(i, n);

		reverse(l_up.begin(), l_up.end());
		string for_a = l_up + "#" + t;
		string for_b = r_up + "#" + t_rev;
		compute(for_a, p1);
		compute(for_b, p2);

		for (int j = 1; j <= m; j++) {
			int a = p1[i+j];
			int b = p2[n+m-i-j];
			if (a + b > ans[0]) {
				ans[0] = a + b;
				ans[1] = i - p1[i+j];
				ans[2] = (rev ? m - j - b : j - a);
			}
		}
	}
}

int main() {
	fast
	string s, t;
	cin >> s >> t;
	n = s.size(), m = t.size();

	solve(s, t, 0);
	reverse(t.begin(), t.end());
	solve(s, t, 1);
	cout << ans[0] << "\n" << ans[1] << " " << ans[2] << "\n";
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 124 ms 604 KB Output is correct
14 Correct 94 ms 604 KB Output is correct
15 Correct 176 ms 592 KB Output is correct
16 Correct 123 ms 568 KB Output is correct
17 Correct 65 ms 548 KB Output is correct
18 Correct 73 ms 600 KB Output is correct
19 Correct 95 ms 604 KB Output is correct
20 Correct 111 ms 596 KB Output is correct
21 Correct 118 ms 600 KB Output is correct