oj.uz

Submission #826515

# Submission time Handle Problem Language Result Execution time Memory
826515 2023-08-15T16:16:59 Z QwertyPi Necklace (Subtask 1-3) (BOI19_necklace1) C++14
17 / 85
 1014 ms 392 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct answer{
	int a, x, y;
};

const int P = 1e9 + 7, A = 13895;
const int N = 3e4 + 11;
int norm(int x){
	return (x % P + P) % P;
}

int h_s[N], h_t[N], pw[N];

int hash_s(int i, int l){
	return norm(h_s[i + l] - h_s[i] * pw[l]);
}

int hash_t(int i, int l){
	return norm(h_t[i + l] - h_t[i] * pw[l]);
}

answer query(const string& s, const string& t){
	int n = s.size(), m = t.size();
	h_s[0] = 0; for(int i = 0; i < n; i++) h_s[i + 1] = (h_s[i] * A + s[i] - 'a') % P;
	h_t[0] = 0; for(int i = 0; i < m; i++) h_t[i + 1] = (h_t[i] * A + t[i] - 'a') % P;
	pw[0] = 1; for(int i = 0; i < max(n, m); i++) pw[i + 1] = pw[i] * A % P;

	answer ans {-1, 0, 0};
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			int lo = 0, hi = min(n - i, m - j);
			while(lo != hi){
				int mid = (lo + hi + 1) / 2;
				if(hash_s(i, mid) == hash_t(j, mid)){
					lo = mid;
				}else{
					hi = mid - 1;
				}
			}
			answer ans_new {lo, i, j};
			if(ans_new.a > ans.a){
				ans = ans_new;
			}
		}
	}
	return ans;
}

int32_t main(){
	string s, t; cin >> s >> t;
	answer a1 = query(s, t);
	reverse(t.begin(), t.end());
	answer a2 = query(s, t); a2.y = t.size() - (a2.y + a2.a);

	answer ans; ans.a = -1;
	if(a1.a > ans.a) ans = a1;
	if(a2.a > ans.a) ans = a2;
	cout << ans.a << endl;
	cout << ans.x << ' ' << ans.y << endl; 
}

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 1 ms 212 KB Output is partially correct
3 Partially correct 1 ms 212 KB Output is partially correct
4 Partially correct 1 ms 212 KB Output is partially correct
5 Partially correct 1 ms 212 KB Output is partially correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 1 ms 212 KB Output is partially correct
3 Partially correct 1 ms 212 KB Output is partially correct
4 Partially correct 1 ms 212 KB Output is partially correct
5 Partially correct 1 ms 212 KB Output is partially correct
6 Partially correct 13 ms 320 KB Output is partially correct
7 Partially correct 12 ms 324 KB Output is partially correct
8 Partially correct 11 ms 212 KB Output is partially correct
9 Partially correct 12 ms 320 KB Output is partially correct
10 Partially correct 11 ms 212 KB Output is partially correct
11 Partially correct 14 ms 324 KB Output is partially correct
12 Partially correct 11 ms 212 KB Output is partially correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 1 ms 212 KB Output is partially correct
3 Partially correct 1 ms 212 KB Output is partially correct
4 Partially correct 1 ms 212 KB Output is partially correct
5 Partially correct 1 ms 212 KB Output is partially correct
6 Partially correct 13 ms 320 KB Output is partially correct
7 Partially correct 12 ms 324 KB Output is partially correct
8 Partially correct 11 ms 212 KB Output is partially correct
9 Partially correct 12 ms 320 KB Output is partially correct
10 Partially correct 11 ms 212 KB Output is partially correct
11 Partially correct 14 ms 324 KB Output is partially correct
12 Partially correct 11 ms 212 KB Output is partially correct
13 Partially correct 1004 ms 380 KB Output is partially correct
14 Partially correct 967 ms 380 KB Output is partially correct
15 Partially correct 948 ms 384 KB Output is partially correct
16 Partially correct 1014 ms 384 KB Output is partially correct
17 Partially correct 865 ms 380 KB Output is partially correct
18 Partially correct 926 ms 392 KB Output is partially correct
19 Partially correct 953 ms 384 KB Output is partially correct
20 Partially correct 1012 ms 384 KB Output is partially correct
21 Partially correct 1004 ms 376 KB Output is partially correct