oj.uz

Submission #421129

# Submission time Handle Problem Language Result Execution time Memory
421129 2021-06-08T18:32:30 Z abdzag Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 3516 KB 
#include<bits/stdc++.h>
#include<unordered_map>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define trav(a,v) for(auto& a: v)
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define vi vector<int>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const long long inf = 1e15;
vector<ull> suffix(1e5);
vector<ull> suffix2(1e5);
vector<ull> suffix3(1e5);
vector<ull> powers(1e5);
ll n;
ull getS(vector<ull>& v, ll start, ll end) {
	if (start >= end)return 0;
	return v[start] - (v[end] * powers[end - start]);
}
int main() {
	cin.sync_with_stdio(false);
	vector<ull> primes = { 43,47,53,59,61,67,71,73,79,83,89,97,101,103,107 };
	string a, b;
	cin >> a >> b;
	n = a.size();
	ull c = primes[rand() % primes.size()];
	powers[0] = 1;
	rep(i, 1, 1e5)powers[i] = powers[i - 1] * c;
	rrep(i, a.size() - 1, -1)suffix[i] = a[i] + c * suffix[i + 1];
	rrep(i, b.size() - 1, -1)suffix2[i] = b[i] + c * suffix2[i + 1];
	reverse(all(a));
	rrep(i, a.size() - 1, -1)suffix3[i] = a[i] + c * suffix3[i + 1];
	ll ans = 0;
	ll pos1, pos2;
	rep(i, 0, b.size()) {
		rep(j, 0, a.size()) {
			int FuckMinAndMax = b.size() - i;
			ll l = 1, r = min(j, FuckMinAndMax);//maybe wrong
			ll val1 = 0;
			rep(mid, l, r + 1) {
				if (getS(suffix2, i, i + mid) == getS(suffix, j - mid, j)) {
					val1 = mid;
				}
			}
			FuckMinAndMax = a.size() - j;
			l = 0, r = min(i, FuckMinAndMax);//maybe wrong
			ll val2 = 0;
			rep(mid, l, r + 1) {
				if (getS(suffix2, i - mid, i) == getS(suffix, j, j + mid)) {
					val2 = mid;
				}
			}
			if (val1 + val2 > ans) {
				ans = val1 + val2;
				pos1 = j - val1;
				pos2 = i - val2;
			}
		}
		rep(j, 0, a.size()) {
			int FuckMinAndMax = b.size() - i;
			ll l = 1, r = min(j, FuckMinAndMax);//maybe wrong
			ll val1 = 0;
			rep(mid, l, r + 1) {
				if (getS(suffix2, i, i + mid) == getS(suffix3, j - mid, j)) {
					val1 = mid;
				}
			}
			FuckMinAndMax = a.size() - j;
			l = 0, r = min(i, FuckMinAndMax);//maybe wrong
			ll val2 = 0;
			rep(mid, l, r + 1) {
				if (getS(suffix2, i - mid, i) == getS(suffix3, j, j + mid)) {
					val2 = mid;
				}
			}
			if (val1 + val2 > ans) {
				ans = val1 + val2;
				pos1 = a.size() - j - val2;
				pos2 = i - val2;
			}
		}
	}
	cout << ans << endl;
	if (ans)cout << pos1 << " " << pos2 << endl;
	return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3404 KB Output is correct
2 Correct 5 ms 3468 KB Output is correct
3 Correct 4 ms 3404 KB Output is correct
4 Correct 4 ms 3404 KB Output is correct
5 Correct 4 ms 3472 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3404 KB Output is correct
2 Correct 5 ms 3468 KB Output is correct
3 Correct 4 ms 3404 KB Output is correct
4 Correct 4 ms 3404 KB Output is correct
5 Correct 4 ms 3472 KB Output is correct
6 Correct 189 ms 3448 KB Output is correct
7 Correct 167 ms 3404 KB Output is correct
8 Correct 119 ms 3448 KB Output is correct
9 Correct 150 ms 3448 KB Output is correct
10 Correct 142 ms 3516 KB Output is correct
11 Correct 188 ms 3444 KB Output is correct
12 Correct 137 ms 3444 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3404 KB Output is correct
2 Correct 5 ms 3468 KB Output is correct
3 Correct 4 ms 3404 KB Output is correct
4 Correct 4 ms 3404 KB Output is correct
5 Correct 4 ms 3472 KB Output is correct
6 Correct 189 ms 3448 KB Output is correct
7 Correct 167 ms 3404 KB Output is correct
8 Correct 119 ms 3448 KB Output is correct
9 Correct 150 ms 3448 KB Output is correct
10 Correct 142 ms 3516 KB Output is correct
11 Correct 188 ms 3444 KB Output is correct
12 Correct 137 ms 3444 KB Output is correct
13 Execution timed out 1580 ms 3404 KB Time limit exceeded
14 Halted 0 ms 0 KB -