oj.uz

Submission #422865

# Submission time Handle Problem Language Result Execution time Memory
422865 2021-06-10T13:16:20 Z abdzag Necklace (Subtask 1-3) (BOI19_necklace1) C++17
17 / 85
 383 ms 71128 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 {
				while (b[i + counter] != a[j - 1]&&counter)counter--;
				if (b[i + counter] == a[j - 1])v[i][j] = ++counter;
			}
		}
	}
	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 76 ms 71000 KB Output is partially correct
2 Correct 76 ms 70892 KB Output is correct
3 Correct 82 ms 70916 KB Output is correct
4 Correct 80 ms 71008 KB Output is correct
5 Correct 78 ms 70956 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 76 ms 71000 KB Output is partially correct
2 Correct 76 ms 70892 KB Output is correct
3 Correct 82 ms 70916 KB Output is correct
4 Correct 80 ms 71008 KB Output is correct
5 Correct 78 ms 70956 KB Output is correct
6 Correct 78 ms 70928 KB Output is correct
7 Partially correct 77 ms 71048 KB Output is partially correct
8 Correct 79 ms 71008 KB Output is correct
9 Correct 74 ms 70932 KB Output is correct
10 Correct 77 ms 70904 KB Output is correct
11 Correct 76 ms 71000 KB Output is correct
12 Correct 78 ms 70904 KB Output is correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 76 ms 71000 KB Output is partially correct
2 Correct 76 ms 70892 KB Output is correct
3 Correct 82 ms 70916 KB Output is correct
4 Correct 80 ms 71008 KB Output is correct
5 Correct 78 ms 70956 KB Output is correct
6 Correct 78 ms 70928 KB Output is correct
7 Partially correct 77 ms 71048 KB Output is partially correct
8 Correct 79 ms 71008 KB Output is correct
9 Correct 74 ms 70932 KB Output is correct
10 Correct 77 ms 70904 KB Output is correct
11 Correct 76 ms 71000 KB Output is correct
12 Correct 78 ms 70904 KB Output is correct
13 Correct 380 ms 71032 KB Output is correct
14 Partially correct 383 ms 70936 KB Output is partially correct
15 Correct 365 ms 71128 KB Output is correct
16 Correct 376 ms 71032 KB Output is correct
17 Correct 361 ms 70932 KB Output is correct
18 Correct 356 ms 70960 KB Output is correct
19 Correct 366 ms 70984 KB Output is correct
20 Correct 363 ms 71060 KB Output is correct
21 Correct 362 ms 71120 KB Output is correct