oj.uz

Submission #133110

# Submission time Handle Problem Language Result Execution time Memory
133110 2019-07-20T07:38:13 Z E869120 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
45 / 85
 1500 ms 35888 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];

long long hash_s(int l, int r) {
	// [l, r]
	return as[r + 1] - as[l] * power[r - l + 1];
}

long long hash_t(int l, int r) {
	// [l, r]
	return at[r + 1] - at[l] * power[r - l + 1];
}

int get_pb(int l, int r) {
	int len = 0;
	for (int i = 11; i >= 0; i--) {
		int cx = len + (1 << i);
		if (!(l + cx - 1 < N && r + cx - 1 < M)) continue;
		long long v1 = hash_s(l, l + cx - 1);
		long long v2 = hash_t(r, r + cx - 1);
		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:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) {
                  ~~^~~~~~~~~~
necklace.cpp:39: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 7 ms 888 KB Output is correct
2 Correct 7 ms 888 KB Output is correct
3 Correct 6 ms 808 KB Output is correct
4 Correct 7 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 7 ms 888 KB Output is correct
2 Correct 7 ms 888 KB Output is correct
3 Correct 6 ms 808 KB Output is correct
4 Correct 7 ms 888 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 37 ms 2680 KB Output is correct
7 Correct 38 ms 2748 KB Output is correct
8 Correct 34 ms 2552 KB Output is correct
9 Correct 36 ms 2552 KB Output is correct
10 Correct 38 ms 2680 KB Output is correct
11 Correct 37 ms 2680 KB Output is correct
12 Correct 36 ms 2552 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 888 KB Output is correct
2 Correct 7 ms 888 KB Output is correct
3 Correct 6 ms 808 KB Output is correct
4 Correct 7 ms 888 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 37 ms 2680 KB Output is correct
7 Correct 38 ms 2748 KB Output is correct
8 Correct 34 ms 2552 KB Output is correct
9 Correct 36 ms 2552 KB Output is correct
10 Correct 38 ms 2680 KB Output is correct
11 Correct 37 ms 2680 KB Output is correct
12 Correct 36 ms 2552 KB Output is correct
13 Execution timed out 1566 ms 35888 KB Time limit exceeded
14 Halted 0 ms 0 KB -