Submission #376947

#	Time	Username	Problem	Language	Result	Execution time	Memory
376947		AmShZ	Necklace (Subtask 1-3) (BOI19_necklace1)	C++11	85 / 85	396 ms	71936 KiB

necklace

//khodaya khodet komak kon
# include <bits/stdc++.h>
 
/*
// ordered_set 
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
# define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
*/
 
using namespace std;
 
typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;
 
# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define InTheNameOfGod                                  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
 
const int xn = 3e3 + 10;
const int xm = 10 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int mod = 998244353;
const int base = 257;
 
int n, Rank[xm][xn + xn], pw, lcp[xn + xn];
int ps[2][xn][xn], m, ans, P[xn + xn];
pii ANS;
string S, s, t;
 
bool cmp(int i, int j){
	if (Rank[pw - 1][i] != Rank[pw - 1][j])
		return Rank[pw - 1][i] < Rank[pw - 1][j];
	if (max(i, j) + (1 << (pw - 1)) > SZ(S))
		return i > j;
	return Rank[pw - 1][(1 << (pw - 1)) + i] < Rank[pw - 1][(1 << (pw - 1)) + j];
}
void buildSA(){
	for (int i = 1; i <= SZ(S); ++ i)
		Rank[0][i] = S[i - 1], P[i] = i;
	for (pw = 1; pw < xm; ++ pw){
		sort(P + 1, P + SZ(S) + 1, cmp);
		Rank[pw][P[1]] = 1;
		for (int i = 2; i <= SZ(S); ++ i)
			Rank[pw][P[i]] = Rank[pw][P[i - 1]] + cmp(P[i - 1], P[i]);
	}
}
int LCP(int x, int y){
	int res = 0;
	for (int i = xm - 1; i >= 0; -- i){
		if (Rank[i][x] != Rank[i][y] || max(x, y) + (1 << i) - 1 > SZ(S))
			continue;
		x += 1 << i, y += 1 << i;
		res |= (1 << i);
	}
	return res;
}
void solve(bool fl){
	n = SZ(s), m = SZ(t);
	S = s + char(1) + t;
	buildSA();
	for (int i = 1; i < SZ(S); ++ i)
		lcp[i] = LCP(P[i], P[i + 1]);
	for (int i = 0; i < xn; ++ i)
		for (int j = 0; j < xn; ++ j)
			ps[0][i][j] = j, ps[1][i][j] = i;
	for (int i = 1; i < SZ(S); ++ i){
		int res = inf;
		if (P[i] > n)
			continue;
		for (int j = i; j < SZ(S); ++ j){
			res = min(res, lcp[j]);
			if (P[j + 1] > n + 1){
				int x = P[i];
				int y = P[j + 1] - n - 1;
				ps[0][x][y + res] = min(ps[0][x][y + res], y);
				ps[1][x + res][y] = min(ps[1][x + res][y], x);
			}
		}
		res = inf;
		for (int j = i - 1; j >= 1; -- j){
			res = min(res, lcp[j]);
			if (P[j] > n + 1){
				int x = P[i];
				int y = P[j] - n - 1;
				ps[0][x][y + res] = min(ps[0][x][y + res], y);
				ps[1][x + res][y] = min(ps[1][x + res][y], x);
			}
		}
	}
	for (int i = n + 1; i >= 1; -- i){
		for (int j = m + 1; j >= 1; -- j){
			ps[0][i][j] = min(ps[0][i][j], ps[0][i][j + 1]);
			ps[1][i][j] = min(ps[1][i][j], ps[1][i + 1][j]);
			if (i + j - ps[0][i][j] - ps[1][i][j] > ans){
				ans = i + j - ps[0][i][j] - ps[1][i][j];
				if (!fl)
					ANS = {ps[1][i][j] - 1, ps[0][i][j] - 1};
				else
					ANS = {ps[1][i][j] - 1, m - j - i + ps[1][i][j] + 1};
			}
		}
	}
}

int main(){
	InTheNameOfGod;
 
	cin >> s >> t;
	solve(0);
	reverse(all(t));
	solve(1);
	cout << ans << endl;
	cout << ANS.A << sep << ANS.B << endl;
 
	return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40