oj.uz

Submission #867029

# Submission time Handle Problem Language Result Execution time Memory
867029 2023-10-27T15:16:18 Z serifefedartar Necklace (Subtask 1-3) (BOI19_necklace1) C++17
0 / 85
 2 ms 436 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(t.begin(), t.end());
		string for_b = r_up + "#" + t;
		reverse(l_up.begin(), l_up.end());
		reverse(t.begin(), t.end());
		string for_a = l_up + "#" + t;
		int len_b = r_up.length() + 1;
		int len_a = l_up.length() + 1;
		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.length(), m = t.length();

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

Compilation message

necklace.cpp: In function 'void solve(std::string, std::string, bool)':
necklace.cpp:41:7: warning: unused variable 'len_b' [-Wunused-variable]
   41 |   int len_b = r_up.length() + 1;
      |       ^~~~~
necklace.cpp:42:7: warning: unused variable 'len_a' [-Wunused-variable]
   42 |   int len_a = l_up.length() + 1;
      |       ^~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -