oj.uz

Submission #422815

# Submission time Handle Problem Language Result Execution time Memory
422815 2021-06-10T12:44:47 Z abdzag Necklace (Subtask 1-3) (BOI19_necklace1) C++17
17 / 85
 431 ms 71196 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;
		}
	}
	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 77 ms 71000 KB Output is partially correct
2 Correct 76 ms 70844 KB Output is correct
3 Correct 76 ms 70924 KB Output is correct
4 Correct 74 ms 70860 KB Output is correct
5 Correct 75 ms 71040 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 77 ms 71000 KB Output is partially correct
2 Correct 76 ms 70844 KB Output is correct
3 Correct 76 ms 70924 KB Output is correct
4 Correct 74 ms 70860 KB Output is correct
5 Correct 75 ms 71040 KB Output is correct
6 Partially correct 76 ms 70932 KB Output is partially correct
7 Partially correct 78 ms 70968 KB Output is partially correct
8 Correct 77 ms 71068 KB Output is correct
9 Correct 85 ms 70980 KB Output is correct
10 Correct 77 ms 70812 KB Output is correct
11 Correct 88 ms 70860 KB Output is correct
12 Correct 76 ms 70848 KB Output is correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 77 ms 71000 KB Output is partially correct
2 Correct 76 ms 70844 KB Output is correct
3 Correct 76 ms 70924 KB Output is correct
4 Correct 74 ms 70860 KB Output is correct
5 Correct 75 ms 71040 KB Output is correct
6 Partially correct 76 ms 70932 KB Output is partially correct
7 Partially correct 78 ms 70968 KB Output is partially correct
8 Correct 77 ms 71068 KB Output is correct
9 Correct 85 ms 70980 KB Output is correct
10 Correct 77 ms 70812 KB Output is correct
11 Correct 88 ms 70860 KB Output is correct
12 Correct 76 ms 70848 KB Output is correct
13 Correct 370 ms 71012 KB Output is correct
14 Partially correct 431 ms 70932 KB Output is partially correct
15 Correct 390 ms 71068 KB Output is correct
16 Correct 380 ms 71060 KB Output is correct
17 Correct 344 ms 70936 KB Output is correct
18 Correct 355 ms 70876 KB Output is correct
19 Correct 384 ms 71196 KB Output is correct
20 Correct 367 ms 70860 KB Output is correct
21 Correct 369 ms 71068 KB Output is correct