oj.uz

답안 #530089

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
530089 2022-02-24T14:52:23 Z fatemetmhr Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 588 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 && 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 = 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 + 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);
	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:134:25: warning: 'ids' may be used uninitialized in this function [-Wmaybe-uninitialized]
  134 |  return {ans, {ids, idt}};
      |                         ^
necklace.cpp:134:25: warning: 'idt' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
25.0 / 25.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 8 ms 416 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 6 ms 332 KB Output is correct
6 Correct 190 ms 428 KB Output is correct
7 Correct 158 ms 432 KB Output is correct
8 Correct 151 ms 332 KB Output is correct
9 Correct 145 ms 428 KB Output is correct
10 Correct 113 ms 436 KB Output is correct
11 Correct 119 ms 444 KB Output is correct
12 Correct 142 ms 428 KB Output is correct

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 8 ms 416 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 6 ms 332 KB Output is correct
6 Correct 190 ms 428 KB Output is correct
7 Correct 158 ms 432 KB Output is correct
8 Correct 151 ms 332 KB Output is correct
9 Correct 145 ms 428 KB Output is correct
10 Correct 113 ms 436 KB Output is correct
11 Correct 119 ms 444 KB Output is correct
12 Correct 142 ms 428 KB Output is correct
13 Execution timed out 1584 ms 588 KB Time limit exceeded
14 Halted 0 ms 0 KB -