oj.uz

Submission #376982

# Submission time Handle Problem Language Result Execution time Memory
376982 2021-03-12T14:16:02 Z sinamhdv Necklace (Subtask 1-3) (BOI19_necklace1) C++11
45 / 85
 1164 ms 73068 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 += (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 52 ms 72812 KB Output is correct
2 Correct 52 ms 72812 KB Output is correct
3 Correct 53 ms 72812 KB Output is correct
4 Correct 58 ms 72812 KB Output is correct
5 Correct 54 ms 72852 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 72812 KB Output is correct
2 Correct 52 ms 72812 KB Output is correct
3 Correct 53 ms 72812 KB Output is correct
4 Correct 58 ms 72812 KB Output is correct
5 Correct 54 ms 72852 KB Output is correct
6 Correct 69 ms 72812 KB Output is correct
7 Correct 71 ms 72940 KB Output is correct
8 Correct 65 ms 72832 KB Output is correct
9 Correct 66 ms 72812 KB Output is correct
10 Correct 65 ms 72812 KB Output is correct
11 Correct 66 ms 72812 KB Output is correct
12 Correct 65 ms 72812 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 72812 KB Output is correct
2 Correct 52 ms 72812 KB Output is correct
3 Correct 53 ms 72812 KB Output is correct
4 Correct 58 ms 72812 KB Output is correct
5 Correct 54 ms 72852 KB Output is correct
6 Correct 69 ms 72812 KB Output is correct
7 Correct 71 ms 72940 KB Output is correct
8 Correct 65 ms 72832 KB Output is correct
9 Correct 66 ms 72812 KB Output is correct
10 Correct 65 ms 72812 KB Output is correct
11 Correct 66 ms 72812 KB Output is correct
12 Correct 65 ms 72812 KB Output is correct
13 Correct 1164 ms 73068 KB Output is correct
14 Correct 940 ms 72940 KB Output is correct
15 Correct 1071 ms 72832 KB Output is correct
16 Correct 974 ms 73068 KB Output is correct
17 Correct 773 ms 72964 KB Output is correct
18 Correct 806 ms 72812 KB Output is correct
19 Correct 929 ms 72964 KB Output is correct
20 Correct 1006 ms 73068 KB Output is correct
21 Incorrect 1022 ms 72940 KB Output isn't correct