oj.uz

Submission #124931

# Submission time Handle Problem Language Result Execution time Memory
124931 2019-07-04T07:30:50 Z 윤교준(#3050) Necklace (Subtask 1-3) (BOI19_necklace1) C++14
45 / 85
 1500 ms 384 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;

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;
}

int L[3005], R[3005];
void process() {
	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(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(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:56: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 4 ms 384 KB Output is correct
2 Correct 3 ms 296 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 3 ms 296 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 109 ms 376 KB Output is correct
7 Correct 42 ms 384 KB Output is correct
8 Correct 19 ms 376 KB Output is correct
9 Correct 13 ms 376 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 7 ms 376 KB Output is correct
12 Correct 22 ms 376 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 3 ms 296 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 109 ms 376 KB Output is correct
7 Correct 42 ms 384 KB Output is correct
8 Correct 19 ms 376 KB Output is correct
9 Correct 13 ms 376 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 7 ms 376 KB Output is correct
12 Correct 22 ms 376 KB Output is correct
13 Execution timed out 1553 ms 376 KB Time limit exceeded
14 Halted 0 ms 0 KB -