oj.uz

Submission #124879

# Submission time Handle Problem Language Result Execution time Memory
124879 2019-07-04T05:13:46 Z 윤교준(#3050) Necklace (Subtask 1-3) (BOI19_necklace1) C++14
0 / 85
 979 ms 508 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;

// 1000002173, 6481
// 1000053209, 20063

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

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

	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[e] - ll(T[e-s+1]) * B[s-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[6005];

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 < 6005; 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 = 1; i <= M*2; i++)
		hsh.B[i] = (ll(hsh.B[i-1]) * KEY + (B[i]-'a')) % MOD;
}

void process() {
	precal(hsh);

	for(int l = min(N, M); l; l--) {
		for(int as = 1, ae = l; ae <= N; as++, ae++) {
			for(int bs = 1, be = l; bs <= M; bs++, be++) {
				for(int i = bs; i < be; i++) {
					int delta = be-(i+1);
					if(hsh.cmp(as, i+1, delta+1) && hsh.cmp(as+delta+1, bs, l-delta-1)) {
						upd(l, as, bs);
						return;
					}
				}
			}
		}
	}
}

int main() {
	scanf(" %s %s", A+1, B+1);
	N = strlen(A+1);
	M = strlen(B+1);
	for(int i = 1; i <= M; i++) B[M+i] = B[i];

	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:75: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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 504 KB Output is correct
2 Correct 98 ms 508 KB Output is correct
3 Correct 698 ms 376 KB Output is correct
4 Incorrect 979 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 504 KB Output is correct
2 Correct 98 ms 508 KB Output is correct
3 Correct 698 ms 376 KB Output is correct
4 Incorrect 979 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 504 KB Output is correct
2 Correct 98 ms 508 KB Output is correct
3 Correct 698 ms 376 KB Output is correct
4 Incorrect 979 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -