oj.uz

Submission #133115

# Submission time Handle Problem Language Result Execution time Memory
133115 2019-07-20T07:41:10 Z E869120 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
45 / 85
 1484 ms 36088 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] * 101LL;
		as[i + 1] += (S[i] - 'a' + 1);
	}
	for (int i = 0; i < T.size(); i++) {
		at[i + 1] += at[i] * 101LL;
		at[i + 1] += (T[i] - 'a' + 1);
	}
	power[0] = 1; for (int i = 1; i <= 3000; i++) power[i] = (101LL * 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 888 KB Output is correct
2 Correct 6 ms 888 KB Output is correct
3 Correct 6 ms 832 KB Output is correct
4 Correct 6 ms 888 KB Output is correct
5 Correct 7 ms 888 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 888 KB Output is correct
2 Correct 6 ms 888 KB Output is correct
3 Correct 6 ms 832 KB Output is correct
4 Correct 6 ms 888 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 35 ms 2680 KB Output is correct
7 Correct 36 ms 2748 KB Output is correct
8 Correct 32 ms 2552 KB Output is correct
9 Correct 35 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 33 ms 2552 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 888 KB Output is correct
2 Correct 6 ms 888 KB Output is correct
3 Correct 6 ms 832 KB Output is correct
4 Correct 6 ms 888 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 35 ms 2680 KB Output is correct
7 Correct 36 ms 2748 KB Output is correct
8 Correct 32 ms 2552 KB Output is correct
9 Correct 35 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 33 ms 2552 KB Output is correct
13 Correct 1477 ms 35960 KB Output is correct
14 Correct 1484 ms 36088 KB Output is correct
15 Correct 1394 ms 34552 KB Output is correct
16 Correct 1476 ms 35832 KB Output is correct
17 Correct 1432 ms 35248 KB Output is correct
18 Correct 1476 ms 35872 KB Output is correct
19 Incorrect 1470 ms 35704 KB Output isn't correct
20 Halted 0 ms 0 KB -