oj.uz

Submission #376971

# Submission time Handle Problem Language Result Execution time Memory
376971 2021-03-12T13:34:25 Z sinamhdv Necklace (Subtask 1-3) (BOI19_necklace1) C++11
45 / 85
 1500 ms 72428 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 sph[MAXN], tph[MAXN];
int pw[MAXN];
int ans;
int sind, tind;

inline void prehash(const string &s, int *ph)
{
	FOR(i, 1, (int)s.size() + 1)
	{
		ph[i] = ((ll)ph[i - 1] * prm + s[i - 1]) % mod;
	}
}

inline ll gethash(int *ph, int l, int r)
{
	int res = ph[r + 1] - (ll)ph[l] * pw[r - l + 1] % mod;
	return (mod + res) % mod;
}

inline int getlcp(int x, int y)
{
	if (s[x] != t[y]) return 0;
	int l = 1;
	int r = min(n - x, m - y) + 1;
	while (r - l > 1)
	{
		int mid = (r + l) / 2;
		if (gethash(sph, x, x + mid - 1) == gethash(tph, y, y + mid - 1))
			l = mid;
		else
			r = mid;
	}
	return l;
}

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

void solve(bool rev)
{
	memset(sph, 0, sizeof(sph));
	memset(tph, 0, sizeof(tph));
	prehash(s, sph);
	prehash(t, tph);
	memset(kmp, 0, sizeof(kmp));

	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, 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();

	pw[0] = 1;
	FOR(i, 1, MAXN)
	{
		pw[i] = (ll)pw[i - 1] * prm % mod;
	}

	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 72300 KB Output is correct
2 Correct 51 ms 72300 KB Output is correct
3 Correct 56 ms 72300 KB Output is correct
4 Correct 48 ms 72300 KB Output is correct
5 Correct 47 ms 72300 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 72300 KB Output is correct
2 Correct 51 ms 72300 KB Output is correct
3 Correct 56 ms 72300 KB Output is correct
4 Correct 48 ms 72300 KB Output is correct
5 Correct 47 ms 72300 KB Output is correct
6 Correct 79 ms 72300 KB Output is correct
7 Correct 63 ms 72300 KB Output is correct
8 Correct 77 ms 72300 KB Output is correct
9 Correct 66 ms 72300 KB Output is correct
10 Correct 52 ms 72300 KB Output is correct
11 Correct 53 ms 72428 KB Output is correct
12 Correct 73 ms 72300 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 72300 KB Output is correct
2 Correct 51 ms 72300 KB Output is correct
3 Correct 56 ms 72300 KB Output is correct
4 Correct 48 ms 72300 KB Output is correct
5 Correct 47 ms 72300 KB Output is correct
6 Correct 79 ms 72300 KB Output is correct
7 Correct 63 ms 72300 KB Output is correct
8 Correct 77 ms 72300 KB Output is correct
9 Correct 66 ms 72300 KB Output is correct
10 Correct 52 ms 72300 KB Output is correct
11 Correct 53 ms 72428 KB Output is correct
12 Correct 73 ms 72300 KB Output is correct
13 Execution timed out 1587 ms 72428 KB Time limit exceeded
14 Halted 0 ms 0 KB -