oj.uz

Submission #867040

# Submission time Handle Problem Language Result Execution time Memory
867040 2023-10-27T15:22:50 Z serifefedartar Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 896 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) {
	for (int i = 0; i < n; i++) {
		string l_up = "", r_up = "";
		for (int j = 0; j < i; j++)
			l_up = l_up + s[j];
		for (int j = i; j < n; j++)
			r_up = r_up + s[j];

		reverse(l_up.begin(), l_up.end());
		string for_a = l_up + "#" + t;
		reverse(t.begin(), t.end());
		string for_b = r_up + "#" + t;
		reverse(t.begin(), t.end());
		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 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 472 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 472 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 17 ms 348 KB Output is correct
7 Correct 16 ms 344 KB Output is correct
8 Correct 17 ms 348 KB Output is correct
9 Correct 15 ms 348 KB Output is correct
10 Correct 15 ms 348 KB Output is correct
11 Correct 16 ms 352 KB Output is correct
12 Correct 18 ms 348 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 472 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 17 ms 348 KB Output is correct
7 Correct 16 ms 344 KB Output is correct
8 Correct 17 ms 348 KB Output is correct
9 Correct 15 ms 348 KB Output is correct
10 Correct 15 ms 348 KB Output is correct
11 Correct 16 ms 352 KB Output is correct
12 Correct 18 ms 348 KB Output is correct
13 Execution timed out 1548 ms 896 KB Time limit exceeded
14 Halted 0 ms 0 KB -