oj.uz

Submission #376992

# Submission time Handle Problem Language Result Execution time Memory
376992 2021-03-12T15:37:14 Z sinamhdv Necklace (Subtask 1-3) (BOI19_necklace1) C++11
45 / 85
 1500 ms 72320 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 int 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)
{

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

	prehash(s, sph);
	prehash(t, tph);
	solve(0);

	reverse(all(t));
	memset(tph, 0, sizeof(tph));
	prehash(t, tph);
	memset(kmp, 0, sizeof(kmp));
	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 42 ms 72172 KB Output is correct
2 Correct 41 ms 72172 KB Output is correct
3 Correct 42 ms 72172 KB Output is correct
4 Correct 41 ms 72300 KB Output is correct
5 Correct 41 ms 72172 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 72172 KB Output is correct
2 Correct 41 ms 72172 KB Output is correct
3 Correct 42 ms 72172 KB Output is correct
4 Correct 41 ms 72300 KB Output is correct
5 Correct 41 ms 72172 KB Output is correct
6 Correct 75 ms 72300 KB Output is correct
7 Correct 56 ms 72300 KB Output is correct
8 Correct 70 ms 72300 KB Output is correct
9 Correct 60 ms 72320 KB Output is correct
10 Correct 45 ms 72300 KB Output is correct
11 Correct 46 ms 72300 KB Output is correct
12 Correct 62 ms 72300 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 72172 KB Output is correct
2 Correct 41 ms 72172 KB Output is correct
3 Correct 42 ms 72172 KB Output is correct
4 Correct 41 ms 72300 KB Output is correct
5 Correct 41 ms 72172 KB Output is correct
6 Correct 75 ms 72300 KB Output is correct
7 Correct 56 ms 72300 KB Output is correct
8 Correct 70 ms 72300 KB Output is correct
9 Correct 60 ms 72320 KB Output is correct
10 Correct 45 ms 72300 KB Output is correct
11 Correct 46 ms 72300 KB Output is correct
12 Correct 62 ms 72300 KB Output is correct
13 Execution timed out 1578 ms 72296 KB Time limit exceeded
14 Halted 0 ms 0 KB -