oj.uz

Submission #376989

# Submission time Handle Problem Language Result Execution time Memory
376989 2021-03-12T15:23:06 Z sinamhdv Necklace (Subtask 1-3) (BOI19_necklace1) C++11
85 / 85
 1012 ms 73084 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
#define LOGN 22

string s, t;
int n, m;
int ans;
int sind, tind;
int rnk[LOGN][2 * MAXN];
pair<pii, int> order[2 * MAXN];

inline int getlcp(int x, int y)
{
	int fr = x;
	for (int i = LOGN - 1; i >= 0; i--)
	{
		if (rnk[i][x] == rnk[i][y] && x < n && y-n-1 < m)
		{
			x += (1 << i);
			y += (1 << i);
		}
	}
	return x - fr;
}

int kmp[MAXN][2 * MAXN];

inline int getblcp(int x, int y)
{
	if (x >= n || y < 0) return 0;
	return kmp[x][y + n - x + 2];
}


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;
	}
}

inline void sufarr(const string &s)
{
	int n = s.size();
	FOR(i, 0, n)
	{
		rnk[0][i] = (int)s[i];
	}
	FOR(i, 1, LOGN)
	{
		FOR(j, 0, n)
		{
			pii &p = order[j].fr;
			p.fr = rnk[i - 1][j];
			if (j + (1 << (i - 1)) >= n)
			{
				p.sc = -1;
			}
			else
			{
				p.sc = rnk[i - 1][j + (1 << (i - 1))];
			}
			order[j].sc = j;
		}
		sort(order, order + n);
		FOR(j, 0, n)
		{
			if (j > 0 && order[j].fr == order[j - 1].fr)
			{
				rnk[i][order[j].sc] = rnk[i][order[j - 1].sc];
			}
			else
			{
				rnk[i][order[j].sc] = j;
			}
		}
	}
}

void solve(bool rev)
{
	memset(kmp, 0, sizeof(kmp));
	memset(rnk, 0, sizeof(rnk));
	FOR(i, 0, 2 * MAXN)
		order[i] = {{0, 0}, 0};

	string nw = s + '#' + t;
	sufarr(nw);

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

	FOR(i, 0, n)
	{
		FOR(j, 0, m)
		{
			int lcp = getlcp(i, n + 1 + j);
			int blcp = getblcp(i + lcp, j - 1);
			if (lcp + blcp > ans)
			{
				ans = lcp + blcp;
				sind = i;
				tind = (rev ? m - 1 - (j + lcp - 1) : j - blcp);
			}
		}
	}
}

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 51 ms 72812 KB Output is correct
2 Correct 51 ms 72812 KB Output is correct
3 Correct 51 ms 72832 KB Output is correct
4 Correct 50 ms 72812 KB Output is correct
5 Correct 52 ms 72812 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 72812 KB Output is correct
2 Correct 51 ms 72812 KB Output is correct
3 Correct 51 ms 72832 KB Output is correct
4 Correct 50 ms 72812 KB Output is correct
5 Correct 52 ms 72812 KB Output is correct
6 Correct 66 ms 72812 KB Output is correct
7 Correct 64 ms 72812 KB Output is correct
8 Correct 64 ms 72892 KB Output is correct
9 Correct 64 ms 72888 KB Output is correct
10 Correct 62 ms 72812 KB Output is correct
11 Correct 62 ms 72812 KB Output is correct
12 Correct 63 ms 72812 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 72812 KB Output is correct
2 Correct 51 ms 72812 KB Output is correct
3 Correct 51 ms 72832 KB Output is correct
4 Correct 50 ms 72812 KB Output is correct
5 Correct 52 ms 72812 KB Output is correct
6 Correct 66 ms 72812 KB Output is correct
7 Correct 64 ms 72812 KB Output is correct
8 Correct 64 ms 72892 KB Output is correct
9 Correct 64 ms 72888 KB Output is correct
10 Correct 62 ms 72812 KB Output is correct
11 Correct 62 ms 72812 KB Output is correct
12 Correct 63 ms 72812 KB Output is correct
13 Correct 1012 ms 72940 KB Output is correct
14 Correct 850 ms 72992 KB Output is correct
15 Correct 892 ms 73068 KB Output is correct
16 Correct 881 ms 73084 KB Output is correct
17 Correct 630 ms 72940 KB Output is correct
18 Correct 649 ms 72940 KB Output is correct
19 Correct 786 ms 73068 KB Output is correct
20 Correct 884 ms 73068 KB Output is correct
21 Correct 892 ms 73032 KB Output is correct