oj.uz

Submission #376995

# Submission time Handle Problem Language Result Execution time Memory
376995 2021-03-12T16:04:01 Z sinamhdv Necklace (Subtask 1-3) (BOI19_necklace1) C++11
85 / 85
 502 ms 144364 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;
const int prm = 727;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 3030

string s, t;
int n, m;
int ans;
int sind, tind;
int kmp[2][MAXN][2 * MAXN];

inline void prekmp(const string &s, int *pre)
{
	int cur = 0;
	FOR(i, 1, (int)s.size())
	{
		while (cur > 0 && s[i] != s[cur])
		{
			cur = pre[cur];
		}
		if (s[i] == s[cur])
			cur++;
		pre[i + 1] = cur;
	}
}

void solve(bool rev)
{
	memset(kmp, 0, sizeof(kmp));

	FOR(i, 0, n)
	{
		string tmp = s.substr(i) + '#' + t;
		prekmp(tmp, kmp[0][i]);
	}
	FOR(i, 0, m)
	{
		string tmp = t.substr(i) + '#' + s;
		prekmp(tmp, kmp[1][i]);
	}

	FOR(i, 0, n)
	{
		FOR(j, 0, m)
		{
			int l = kmp[1][j][i + m - j + 2];
			int r = (j == 0 || i == n - 1 ? 0 : kmp[0][i + 1][j - 1 + n - (i + 1) + 2]);
			if (l + r > ans)
			{
				ans = l + r;
				sind = i - l + 1;
				tind = (!rev ? j - r : m - 1 - (j + l - 1));
			}
		}
	}
}

int32_t main(void)
{
	fast_io;
	cin >> s >> t;
	n = s.size();
	m = t.size();

	solve(0);

	reverse(all(t));
	solve(1);
	
	cout << ans << endl;
	cout << sind << ' ' << tind << endl;
	return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 144108 KB Output is correct
2 Correct 98 ms 144108 KB Output is correct
3 Correct 98 ms 144108 KB Output is correct
4 Correct 99 ms 144112 KB Output is correct
5 Correct 98 ms 144108 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 144108 KB Output is correct
2 Correct 98 ms 144108 KB Output is correct
3 Correct 98 ms 144108 KB Output is correct
4 Correct 99 ms 144112 KB Output is correct
5 Correct 98 ms 144108 KB Output is correct
6 Correct 103 ms 144108 KB Output is correct
7 Correct 103 ms 144236 KB Output is correct
8 Correct 104 ms 144108 KB Output is correct
9 Correct 100 ms 144108 KB Output is correct
10 Correct 103 ms 144108 KB Output is correct
11 Correct 103 ms 144108 KB Output is correct
12 Correct 109 ms 144236 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 144108 KB Output is correct
2 Correct 98 ms 144108 KB Output is correct
3 Correct 98 ms 144108 KB Output is correct
4 Correct 99 ms 144112 KB Output is correct
5 Correct 98 ms 144108 KB Output is correct
6 Correct 103 ms 144108 KB Output is correct
7 Correct 103 ms 144236 KB Output is correct
8 Correct 104 ms 144108 KB Output is correct
9 Correct 100 ms 144108 KB Output is correct
10 Correct 103 ms 144108 KB Output is correct
11 Correct 103 ms 144108 KB Output is correct
12 Correct 109 ms 144236 KB Output is correct
13 Correct 502 ms 144108 KB Output is correct
14 Correct 462 ms 144264 KB Output is correct
15 Correct 502 ms 144236 KB Output is correct
16 Correct 463 ms 144236 KB Output is correct
17 Correct 469 ms 144280 KB Output is correct
18 Correct 481 ms 144236 KB Output is correct
19 Correct 501 ms 144236 KB Output is correct
20 Correct 487 ms 144364 KB Output is correct
21 Correct 470 ms 144108 KB Output is correct