oj.uz

답안 #376947

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
376947 2021-03-12T09:41:51 Z AmShZ Necklace (Subtask 1-3) (BOI19_necklace1) C++11
85 / 85
 396 ms 71936 KB 
//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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 71404 KB Output is correct
2 Correct 56 ms 71404 KB Output is correct
3 Correct 56 ms 71532 KB Output is correct
4 Correct 55 ms 71412 KB Output is correct
5 Correct 58 ms 71404 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 71404 KB Output is correct
2 Correct 56 ms 71404 KB Output is correct
3 Correct 56 ms 71532 KB Output is correct
4 Correct 55 ms 71412 KB Output is correct
5 Correct 58 ms 71404 KB Output is correct
6 Correct 62 ms 71404 KB Output is correct
7 Correct 62 ms 71404 KB Output is correct
8 Correct 60 ms 71404 KB Output is correct
9 Correct 61 ms 71552 KB Output is correct
10 Correct 63 ms 71404 KB Output is correct
11 Correct 63 ms 71404 KB Output is correct
12 Correct 61 ms 71404 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 71404 KB Output is correct
2 Correct 56 ms 71404 KB Output is correct
3 Correct 56 ms 71532 KB Output is correct
4 Correct 55 ms 71412 KB Output is correct
5 Correct 58 ms 71404 KB Output is correct
6 Correct 62 ms 71404 KB Output is correct
7 Correct 62 ms 71404 KB Output is correct
8 Correct 60 ms 71404 KB Output is correct
9 Correct 61 ms 71552 KB Output is correct
10 Correct 63 ms 71404 KB Output is correct
11 Correct 63 ms 71404 KB Output is correct
12 Correct 61 ms 71404 KB Output is correct
13 Correct 363 ms 71808 KB Output is correct
14 Correct 317 ms 71916 KB Output is correct
15 Correct 363 ms 71788 KB Output is correct
16 Correct 374 ms 71788 KB Output is correct
17 Correct 379 ms 71924 KB Output is correct
18 Correct 396 ms 71936 KB Output is correct
19 Correct 345 ms 71916 KB Output is correct
20 Correct 341 ms 71916 KB Output is correct
21 Correct 342 ms 71916 KB Output is correct