oj.uz

답안 #530086

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
530086 2022-02-24T14:40:14 Z fatemetmhr Necklace (Subtask 1-3) (BOI19_necklace1) C++17
25 / 85
 220 ms 428 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb     push_back
#define fi     first
#define se     second
#define all(x) x.begin(), x.end()

const int maxn5 = 4e3 + 10;

int n, m;
int mod[2] = {1000000007, 1000000009};
ll base[2] = {37, 31};

ll pw[2][maxn5];
ll has[4][2][maxn5];
vector <pair<int, int>> av, qu;


inline ll get_hash(int ty, int id, int l, int r){
	if(l == 0)
		return has[ty][id][r];
	return (mod[id] + has[ty][id][r] - has[ty][id][l - 1] * pw[id][r - l + 1] % mod[id]) % mod[id];
}

inline bool same(int ty1, int l1, int ty2, int l2, int len){
	if(ty1 == 0 && len > n)
		return false;
	if(ty1 == 1 && len > m)
		return false;
	if(ty1 == 2 && len > n)
		return false;
	if(ty1 == 3 && len > m)
		return false;
	if(ty2 == 0 && len > n)
		return false;
	if(ty2 == 1 && len > m)
		return false;
	if(ty2 == 2 && len > n)
		return false;
	if(ty2 == 3 && len > m)
		return false;
	
	if(get_hash(ty1, 0, l1, l1 + len - 1) != get_hash(ty2, 0, l2, l2 + len - 1))
		return false;
	if(get_hash(ty1, 1, l1, l1 + len - 1) != get_hash(ty2, 1, l2, l2 + len - 1))
		return false;
	return true;
}

inline int lcp(int ty1, int id1, int ty2, int id2){
	int l = 0, r = max(n, m) + 1;
	while(r - l > 1){
		int mid = (l + r) >> 1;
		if(same(ty1, id1, ty2, id2, mid))
			l = mid;
		else
			r = mid;
	}
	return l;
}

inline pair<int, pair<int, int>> solve(string s, string t){
	
	//cout << "wow! " << endl;
	n = s.size(); 
	m = t.size();
	string sp = s, tp = t;
	reverse(sp.begin(), sp.end());
	reverse(tp.begin(), tp.end());
	
	for(int j = 0; j < 2; j++){
		pw[j][0] = 1;
		for(int i = 1; i < maxn5; i++)
			pw[j][i] = pw[j][i - 1] * base[j] % mod[j];
		ll cur = 0;
		for(int i = 0; i < n; i++){
			cur = (cur * base[j] + s[i] - 'a' + 1) % mod[j];
			has[0][j][i] = cur;
		}
		cur = 0;
		for(int i = 0; i < m; i++){
			cur = (cur * base[j] + t[i] - 'a' + 1) % mod[j];
			has[1][j][i] = cur;
		}
		cur = 0;
		for(int i = 0; i < n; i++){
			cur = (cur * base[j] + sp[i] - 'a' + 1) % mod[j];
			has[2][j][i] = cur;
		}
		cur = 0;
		for(int i = 0; i < m; i++){
			cur = (cur * base[j] + tp[i] - 'a' + 1) % mod[j];
			has[3][j][i] = cur;
		}
	}
	
	
	int ans = 0, idt, ids;
	
	for(int i = 0; i < m; i++){
		qu.clear();
		av.clear();
		for(int j = 0; j < n; j++){
			int l = lcp(1, i, 0, j);
			qu.pb({l + j, j});
			//cout << i << ' ' << j << ' ' << l << '\n';
			l = i == 0 ? 0 : lcp(3, m - i, 2, n - j - 1);
			av.pb({j - l, j});
			//cout << i << ' ' << j << ' ' << l << '\n';
		}
		sort(all(qu));
		sort(all(av));
		int ind = 0, mx = -1;
		for(auto [val, id] : qu){
			while(ind < av.size() && av[ind].fi <= val){
				mx = max(mx, av[ind].se);
				ind++;
			}
			if(mx - id + 1 >= ans){
				ans = mx - id + 1;
				ids = id;
				idt = i + val - id - 1 - (mx - id + 1) + 1;
			}
		}
	}
	
	return {ans, {ids, idt}};
}


int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	

	string s, t; cin >> s >> t;

	pair <int, pair<int, int>> ans1 = solve(s, t);
	reverse(t.begin(), t.end());
	pair <int, pair<int, int>> ans2 = solve(s, t);
	int len = ans2.fi, id = ans2.se.se;
	id = int(t.size()) - id - 1;
	id -= len - 1;
	ans2.se.se = id;
	
	if(ans1 < ans2)
		ans1 = ans2;
	cout << ans1.fi << '\n' << ans1.se.fi << ' ' << ans1.se.se << '\n';

	
}

Compilation message

necklace.cpp: In function 'std::pair<int, std::pair<int, int> > solve(std::string, std::string)':
necklace.cpp:119:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |    while(ind < av.size() && av[ind].fi <= val){
      |          ~~~~^~~~~~~~~~~
necklace.cpp:131:25: warning: 'ids' may be used uninitialized in this function [-Wmaybe-uninitialized]
  131 |  return {ans, {ids, idt}};
      |                         ^
necklace.cpp:131:25: warning: 'idt' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 332 KB Output is correct
2 Correct 11 ms 332 KB Output is correct
3 Correct 9 ms 332 KB Output is correct
4 Correct 7 ms 332 KB Output is correct
5 Correct 7 ms 332 KB Output is correct

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 332 KB Output is correct
2 Correct 11 ms 332 KB Output is correct
3 Correct 9 ms 332 KB Output is correct
4 Correct 7 ms 332 KB Output is correct
5 Correct 7 ms 332 KB Output is correct
6 Incorrect 220 ms 428 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 332 KB Output is correct
2 Correct 11 ms 332 KB Output is correct
3 Correct 9 ms 332 KB Output is correct
4 Correct 7 ms 332 KB Output is correct
5 Correct 7 ms 332 KB Output is correct
6 Incorrect 220 ms 428 KB Output isn't correct
7 Halted 0 ms 0 KB -