oj.uz

Submission #422844

# Submission time Handle Problem Language Result Execution time Memory
422844 2021-06-10T13:00:32 Z abdzag Necklace (Subtask 1-3) (BOI19_necklace1) C++17
17 / 85
 420 ms 71060 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;

int main() {
	cin.sync_with_stdio(false);
	string a, b;
	cin >> a >> b;
	ll ans = 0;
	ll pos1, pos2;
	vector<vector<ll>> v(3001, vector<ll>(3001));
	rep(i, 0, b.size()) {
		ll counter = 0;
		rep(j, 1, a.size()+1) {
			if (b[i+counter] == a[j-1])v[i][j] = ++counter;
			else counter = 0;
		}
	}
	rep(i, 0, a.size()) {
		ll counter = 0;
		rep(j, 1, b.size() + 1) {
			if (a[i + counter] == b[j-1])counter++;
			else counter = 0;
			if (ans < counter + v[j][i]) {
				ans = counter + v[j][i];
				pos1 = i - v[j][i];
				pos2 = j - counter;
			}
		}
	}
	reverse(all(a));
	v.clear();
	v.resize(3001, vector<ll>(3001, 0));
	rep(i, 0, b.size()) {
		ll counter = 0;
		rep(j, 1, a.size() + 1) {
			if (b[i + counter] == a[j - 1])v[i][j] = ++counter;
			else {
				counter = 0;
				ll cur = j;
				while (cur > 0) {
					cur = v[i][cur - 1];
					if (cur == 0)break;
					if (b[i + cur] == a[cur - 1]) {
						counter = cur;
						break;
					}
				}
			}
		}
	}
	rep(i, 0, a.size()) {
		ll counter = 0;
		rep(j, 1, b.size() + 1) {
			if (a[i + counter] == b[j - 1])counter++;
			else counter = 0;
			if (ans < counter + v[j][i]) {
				ans = counter + v[j][i];
				pos1 = a.size()-i - counter;
				pos2 = j - counter;
			}
		}
	}
	cout << ans << endl;
	if (ans)cout << pos1 << " " << pos2;
	return 0;
}

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 83 ms 70824 KB Output is partially correct
2 Correct 85 ms 71004 KB Output is correct
3 Correct 84 ms 70848 KB Output is correct
4 Partially correct 77 ms 70860 KB Output is partially correct
5 Correct 76 ms 71024 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 83 ms 70824 KB Output is partially correct
2 Correct 85 ms 71004 KB Output is correct
3 Correct 84 ms 70848 KB Output is correct
4 Partially correct 77 ms 70860 KB Output is partially correct
5 Correct 76 ms 71024 KB Output is correct
6 Partially correct 77 ms 71052 KB Output is partially correct
7 Partially correct 87 ms 70860 KB Output is partially correct
8 Correct 91 ms 70896 KB Output is correct
9 Correct 80 ms 70880 KB Output is correct
10 Correct 86 ms 70916 KB Output is correct
11 Correct 89 ms 70908 KB Output is correct
12 Correct 82 ms 70904 KB Output is correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 83 ms 70824 KB Output is partially correct
2 Correct 85 ms 71004 KB Output is correct
3 Correct 84 ms 70848 KB Output is correct
4 Partially correct 77 ms 70860 KB Output is partially correct
5 Correct 76 ms 71024 KB Output is correct
6 Partially correct 77 ms 71052 KB Output is partially correct
7 Partially correct 87 ms 70860 KB Output is partially correct
8 Correct 91 ms 70896 KB Output is correct
9 Correct 80 ms 70880 KB Output is correct
10 Correct 86 ms 70916 KB Output is correct
11 Correct 89 ms 70908 KB Output is correct
12 Correct 82 ms 70904 KB Output is correct
13 Correct 394 ms 71060 KB Output is correct
14 Partially correct 417 ms 70940 KB Output is partially correct
15 Correct 384 ms 70860 KB Output is correct
16 Correct 416 ms 70932 KB Output is correct
17 Correct 375 ms 70916 KB Output is correct
18 Correct 395 ms 71044 KB Output is correct
19 Correct 382 ms 70936 KB Output is correct
20 Correct 368 ms 70932 KB Output is correct
21 Correct 420 ms 70860 KB Output is correct