oj.uz

Submission #124933

# Submission time Handle Problem Language Result Execution time Memory
124933 2019-07-04T07:35:43 Z 윤교준(#3050) Necklace (Subtask 1-3) (BOI19_necklace1) C++14
25 / 85
 1500 ms 504 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[sz(V)-2])
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;

struct HSH {
	HSH(int mod, int key) : MOD(mod), KEY(key) {}
	const int MOD, KEY;

	int T[3005];
	int A[3005], B[3005];

	int getA(int s, int e) {
		return ((A[e] - ll(T[e-s+1]) * A[s-1]) % MOD + MOD) % MOD;
	}
	int getB(int s, int e) {
		return ((B[s] - ll(T[e-s+1]) * B[e+1]) % MOD + MOD) % MOD;
	}
	bool cmp(int a, int b, int l) {
		return getA(a, a+l-1) == getB(b, b+l-1);
	}
} hsh(1000002173, 6481);

char A[3005], B[3005];

int AnsL, AnsI, AnsJ;
int N, M;

bool __isrev;
void upd(int l, int as, int bs) {
	if(l <= AnsL) return;
	AnsL = l;
	AnsI = __isrev ? N-as-l+2 : as;
	AnsJ = bs;
}

void precal(HSH &hsh) {
	const int MOD = hsh.MOD, KEY = hsh.KEY;
	hsh.T[0] = 1;
	for(int i = 1; i < 3005; i++)
		hsh.T[i] = ll(hsh.T[i-1]) * KEY % MOD;
	for(int i = 1; i <= N; i++)
		hsh.A[i] = (ll(hsh.A[i-1]) * KEY + (A[i]-'a')) % MOD;
	for(int i = M; i; i--)
		hsh.B[i] = (ll(hsh.B[i+1]) * KEY + (B[i]-'a')) % MOD;
}

int L[3005], R[3005];
void process() {
	precal(hsh);

	for(int delta = -N+1; delta <= M-1; delta++) {
		memset(L, 0, 3005<<2);
		memset(R, 0, 3005<<2);

		for(int i = 1; i <= N; i++) {
			int as, ae, bs, be;
			as = ae = i;
			bs = be = i+delta;
			for(int l = 1;; l += 2, as--, bs--, ae++, be++) {
				if(as < 1 || N < ae || bs < 1 || M < be) break;
				if(!hsh.cmp(as, bs, l)) break;
				//if(A[as] != B[be] || A[ae] != B[bs]) break;
				upmax(L[ae+1], l);
				upmax(R[as], l);
			}
			as = i; ae = i+1;
			bs = as+delta; be = ae+delta;
			for(int l = 2;; l += 2, as--, bs--, ae++, be++) {
				if(as < 1 || N < ae || bs < 1 || M < be) break;
				if(!hsh.cmp(as, bs, l)) break;
				//if(A[as] != B[be] || A[ae] != B[bs]) break;
				upmax(L[ae+1], l);
				upmax(R[as], l);
			}
		}

		for(int i = 1; i <= N; i++)
			upd(L[i] + R[i], i-L[i], i-L[i]+delta);
	}
}

int main() {
	scanf(" %s %s", A+1, B+1);
	N = strlen(A+1);
	M = strlen(B+1);

	for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++)
		if(A[i] == B[j]) upd(1, i, j);

	process();
	reverse(A+1, A+N+1);
	__isrev = true;
	process();

	cout << AnsL << endl << AnsI-1 << " " << AnsJ-1 << endl;
	return 0;
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s %s", A+1, B+1);
  ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 504 KB Output is correct
2 Correct 17 ms 400 KB Output is correct
3 Correct 8 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 504 KB Output is correct
2 Correct 17 ms 400 KB Output is correct
3 Correct 8 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Execution timed out 1573 ms 380 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 504 KB Output is correct
2 Correct 17 ms 400 KB Output is correct
3 Correct 8 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Execution timed out 1573 ms 380 KB Time limit exceeded
7 Halted 0 ms 0 KB -