oj.uz

Submission #133116

# Submission time Handle Problem Language Result Execution time Memory
133116 2019-07-20T07:42:06 Z E869120 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
45 / 85
 1489 ms 35960 KB 
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;

int N, M, pa[3009][3009]; long long as[3009], at[3009], power[3009];
int EA[6009], EB[6009];

int get_pb(int l, int r) {
	int len = 0;
	for (int i = 11; i >= 0; i--) {
		int cx = len + (1 << i);
		int cl = l + cx - 1, cr = r + cx - 1;
		if (cl >= N || cr >= M) continue;

		long long v1 = as[cl + 1] - as[l] * power[cx];
		long long v2 = at[cr + 1] - at[r] * power[cx];
		if (v1 == v2) len = cx;
	}
	return len;
}

tuple<int, int, int> solve(string S, string T) {
	for (int i = 0; i <= 3000; i++) { as[i] = 0; at[i] = 0; power[i] = 0; }
	for (int i = 0; i < S.size(); i++) {
		as[i + 1] = as[i] * 103LL;
		as[i + 1] += (S[i] - 'a' + 1);
	}
	for (int i = 0; i < T.size(); i++) {
		at[i + 1] += at[i] * 103LL;
		at[i + 1] += (T[i] - 'a' + 1);
	}
	power[0] = 1; for (int i = 1; i <= 3000; i++) power[i] = (103LL * power[i - 1]);

	N = S.size(); M = T.size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			pa[i][j] = 0;
			if (S[i] == T[j]) pa[i][j] = 1;
			if (i >= 1 && j >= 1 && S[i] == T[j]) {
				pa[i][j] = pa[i - 1][j - 1] + 1;
			}
		}
	}

	int maxn = 0; pair<int, int> maxid = make_pair(-1, -1);
	for (int i = 0; i <= N; i++) {
		// S における境界が i の場合
		vector<int> A, B;
		for (int j = 0; j < M; j++) {
			if (i == N) A.push_back(0);
			else A.push_back(get_pb(i, j));
		}
		for (int j = 0; j < M; j++) {
			if (i == 0) B.push_back(0);
			else B.push_back(pa[i - 1][j]);
		}
		for (int j = 0; j <= 6000; j++) { EA[j] = (1 << 29); EB[j] = -(1 << 29); }
		for (int j = 0; j < N; j++) {
			EA[A[j] + j] = min(EA[A[j] + j], j);
			EB[max(0, -B[j] + j + 1)] = max(EB[max(0, -B[j] + j + 1)], j);
		}
		
		// ret1 には条件を満たす最も左のインデックスを記録
		int ret1 = -(1 << 29);
		for (int j = 0; j <= 6000; j++) {
			ret1 = max(ret1, EB[j]);
			int cr = ret1, cl = EA[j];
			if (maxn < cr - cl + 1) {
				maxn = cr - cl + 1;
				maxid = make_pair(i - B[cr], cl);
			}
		}
	}
	return make_tuple(maxn, maxid.first, maxid.second);
}

int main() {
	string A1, B1, B2; cin >> A1 >> B1; B2 = B1; reverse(B2.begin(), B2.end());
	tuple<int, int, int> v1 = solve(A1, B1);
	tuple<int, int, int> v2 = solve(A1, B2);

	cout << max(get<0>(v1), get<0>(v2)) << endl;
	if (get<0>(v1) > get<0>(v2)) cout << get<1>(v1) << " " << get<2>(v1) << endl;
	if (get<0>(v1) <= get<0>(v2)) cout << get<1>(v2) << " " << M - (get<2>(v2) + get<0>(v2)) << endl;
	return 0;
}

Compilation message

necklace.cpp: In function 'std::tuple<int, int, int> solve(std::__cxx11::string, std::__cxx11::string)':
necklace.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) {
                  ~~^~~~~~~~~~
necklace.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < T.size(); i++) {
                  ~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 892 KB Output is correct
2 Correct 7 ms 888 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 6 ms 888 KB Output is correct
5 Correct 6 ms 888 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 892 KB Output is correct
2 Correct 7 ms 888 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 6 ms 888 KB Output is correct
5 Correct 6 ms 888 KB Output is correct
6 Correct 35 ms 2720 KB Output is correct
7 Correct 35 ms 2712 KB Output is correct
8 Correct 32 ms 2552 KB Output is correct
9 Correct 34 ms 2552 KB Output is correct
10 Correct 35 ms 2680 KB Output is correct
11 Correct 35 ms 2680 KB Output is correct
12 Correct 34 ms 2552 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 892 KB Output is correct
2 Correct 7 ms 888 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 6 ms 888 KB Output is correct
5 Correct 6 ms 888 KB Output is correct
6 Correct 35 ms 2720 KB Output is correct
7 Correct 35 ms 2712 KB Output is correct
8 Correct 32 ms 2552 KB Output is correct
9 Correct 34 ms 2552 KB Output is correct
10 Correct 35 ms 2680 KB Output is correct
11 Correct 35 ms 2680 KB Output is correct
12 Correct 34 ms 2552 KB Output is correct
13 Correct 1489 ms 35940 KB Output is correct
14 Correct 1482 ms 35960 KB Output is correct
15 Correct 1401 ms 34680 KB Output is correct
16 Correct 1462 ms 35792 KB Output is correct
17 Correct 1432 ms 35240 KB Output is correct
18 Correct 1479 ms 35960 KB Output is correct
19 Incorrect 1477 ms 35704 KB Output isn't correct
20 Halted 0 ms 0 KB -