oj.uz

답안 #530090

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

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 332 KB Output is correct
2 Correct 7 ms 332 KB Output is correct
3 Correct 5 ms 332 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 7 ms 332 KB Output is correct
2 Correct 7 ms 332 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 6 ms 332 KB Output is correct
6 Correct 137 ms 332 KB Output is correct
7 Correct 137 ms 380 KB Output is correct
8 Correct 117 ms 376 KB Output is correct
9 Correct 135 ms 332 KB Output is correct
10 Correct 136 ms 388 KB Output is correct
11 Correct 128 ms 380 KB Output is correct
12 Correct 130 ms 376 KB Output is correct

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 332 KB Output is correct
2 Correct 7 ms 332 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 6 ms 332 KB Output is correct
6 Correct 137 ms 332 KB Output is correct
7 Correct 137 ms 380 KB Output is correct
8 Correct 117 ms 376 KB Output is correct
9 Correct 135 ms 332 KB Output is correct
10 Correct 136 ms 388 KB Output is correct
11 Correct 128 ms 380 KB Output is correct
12 Correct 130 ms 376 KB Output is correct
13 Execution timed out 1571 ms 460 KB Time limit exceeded
14 Halted 0 ms 0 KB -