답안 #530098

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
530098 2022-02-24T15:08:52 Z fatemetmhr Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
1488 ms 560 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 (has[ty][id][r] - has[ty][id][l - 1] * pw[id][r - l + 1]);
}

inline int get_lim(int ty, int l){
	if(ty == 0 || ty == 2)
		return n - l;
	return m - l;
}

inline bool same(int ty1, int l1, int ty2, int l2, int len){


	//cout << ty1 << ' ' << l1 + len - 1 << ' ' << ty2 << ' ' << l2 + len - 1 << endl;

	/*
	if(ty1 == 0 && l1 + len - 1 >= n)
		return false;
	if(ty1 == 1 && l1 + len - 1 >= m)
		return false;
	if(ty1 == 2 && l1 + len - 1 >= n)
		return false;
	if(ty1 == 3 && l1 + len - 1 >= m)
		return false;
	if(ty2 == 0 && l2 + len - 1 >= n)
		return false;
	if(ty2 == 1 && l2 + len - 1 >= m)
		return false;
	if(ty2 == 2 && l2 + len - 1 >= n)
		return false;
	if(ty2 == 3 && l2 + len - 1 >= 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 = min(get_lim(ty1, id1), get_lim(ty2, id2)) + 1;
	//cout << "here " << ty1 << ' ' << id1 << ' ' << ty2 << ' ' << id2 << ' ' << r << endl;
	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 < 1; j++){
		pw[j][0] = 1;
		for(int i = 1; i < maxn5; i++)
			pw[j][i] = pw[j][i - 1] * base[j];
		ll cur = 0;
		for(int i = 0; i < n; i++){
			cur = (cur * base[j] + s[i] - 'a' + 1);
			has[0][j][i] = cur;
		}
		cur = 0;
		for(int i = 0; i < m; i++){
			cur = (cur * base[j] + t[i] - 'a' + 1);
			has[1][j][i] = cur;
		}
		cur = 0;
		for(int i = 0; i < n; i++){
			cur = (cur * base[j] + sp[i] - 'a' + 1);
			has[2][j][i] = cur;
		}
		cur = 0;
		for(int i = 0; i < m; i++){
			cur = (cur * base[j] + tp[i] - 'a' + 1);
			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 + 1, 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 && mx - id + 1 >= 1){
				ans = mx - id + 1;
				ids = id;
				if(val - id >= ans)
					idt = i;
				else
					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);
	if(s.size() <= 500){
		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:133: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]
  133 |    while(ind < av.size() && av[ind].fi <= val){
      |          ~~~~^~~~~~~~~~~
necklace.cpp:148:25: warning: 'ids' may be used uninitialized in this function [-Wmaybe-uninitialized]
  148 |  return {ans, {ids, idt}};
      |                         ^
necklace.cpp:148:25: warning: 'idt' may be used uninitialized in this function [-Wmaybe-uninitialized]
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 40 ms 380 KB Output is correct
7 Correct 40 ms 332 KB Output is correct
8 Correct 30 ms 332 KB Output is correct
9 Correct 39 ms 332 KB Output is correct
10 Correct 32 ms 332 KB Output is correct
11 Correct 31 ms 332 KB Output is correct
12 Correct 31 ms 332 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 40 ms 380 KB Output is correct
7 Correct 40 ms 332 KB Output is correct
8 Correct 30 ms 332 KB Output is correct
9 Correct 39 ms 332 KB Output is correct
10 Correct 32 ms 332 KB Output is correct
11 Correct 31 ms 332 KB Output is correct
12 Correct 31 ms 332 KB Output is correct
13 Partially correct 1313 ms 540 KB Output is partially correct
14 Partially correct 1474 ms 544 KB Output is partially correct
15 Correct 1290 ms 560 KB Output is correct
16 Partially correct 1488 ms 548 KB Output is partially correct
17 Incorrect 1176 ms 552 KB Output isn't correct
18 Halted 0 ms 0 KB -