oj.uz

Submission #661038

# Submission time Handle Problem Language Result Execution time Memory
661038 2022-11-24T01:08:29 Z GusterGoose27 Necklace (Subtask 1-3) (BOI19_necklace1) C++11
45 / 85
 1500 ms 680976 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 3000;
const int MAX_s = 4501502;
int n, m;
string s1;
string s2;

class Trie;

Trie *rt;
int to_build[MAX_s];
Trie *tries[MAX_s];
int s = 0, e = 0;
int apos = 0;

class Trie {
public:
	int trans[26];
	int len;
	int prv = -1;
	int arr_pos = 0;
	int par;
	char pchar;
	int s_pos;
	Trie(int par = -1, int l = 0, char pchar = 0, int s_pos = 0) : pchar(pchar), par(par), len(l), s_pos(s_pos) {
		if (l == 0) rt = this;
		fill(trans, trans+26, 0);
		tries[apos] = this;
		arr_pos = apos;
		apos++;
	}
	void build() {
		s++;
		for (int i = 0; i < 26; i++) {
			if (trans[i] > 0) {
				to_build[e++] = trans[i];
			}
		}
		if (len == 0) {
			return;
		}
		if (tries[par]->prv == -1) {
			prv = 0;
		}
		else prv = tries[tries[par]->prv]->trans[pchar];
		for (int i = 0; i < 26; i++) {
			if (trans[i] == 0) trans[i] = tries[prv]->trans[i];
		}
	}
	int ins(char c, int p) {
		if (trans[c] == 0) trans[c] = (new Trie(arr_pos, len+1, c, p))->arr_pos;
		return trans[c];
	}
};

char cur_match[2*MAXN];

bool works(int cur, pii &p) {
	bool found = 0;
	for (int i = 0; i <= m-cur; i++) {
		int pos = 0;
		for (int j = i; j < i+cur; j++) {
			pos = tries[pos]->trans[s2[j]-'a'];
			if (tries[pos]->len == cur) {
				p.first = tries[pos]->s_pos;
				p.second = i;
				found = 1;
				break;
			}
		}
		if (!found) {
			for (int j = i; j < i+cur-1; j++) {
				pos = tries[pos]->trans[s2[j]-'a'];
				if (tries[pos]->len == cur) {
					p.first = tries[pos]->s_pos;
					p.second = i;
					found = 1;
					break;
				}
			}
		}
		if (found) break;
	}
	return found;
}

int make_match(pii &p) {
	if (n > 400) {
		int mn = 0;
		int mx = m+1;
		while (mn+1 < mx) {
			int cur = (mn+mx)/2;
			if (works(cur, p)) mn = cur;
			else mx = cur;
		}
		return mn;
	}
	else {
		for (int i = m; i > 0; i--) if (works(i, p)) return i;
	}
}


int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> s1 >> s2;
	// swap(s1, s2);
	n = s1.size();
	m = s2.size();
	new Trie();
	to_build[e++] = 0;
	for (int i = 0; i < n; i++) {
		int cur = 0;
		for (int j = i; j < n; j++) {
			cur = tries[cur]->ins(s1[j]-'a', i);
		}
	}
	while (s < e) tries[to_build[s]]->build();
	pii p1, p2;
	int b1 = make_match(p1);
	for (int i = 0; i < m/2; i++) swap(s2[i], s2[m-1-i]);
	int b2 = make_match(p2);
	p2.second = m-b2-p2.second;
	if (b1 < b2) {
		b1 = b2;
		p1 = p2;
	}
	// swap(p1.first, p1.second);
	cout << b1 << "\n" << p1.first << " " << p1.second << "\n";
}

Compilation message

necklace.cpp: In constructor 'Trie::Trie(int, int, char, int)':
necklace.cpp:28:7: warning: 'Trie::pchar' will be initialized after [-Wreorder]
   28 |  char pchar;
      |       ^~~~~
necklace.cpp:27:6: warning:   'int Trie::par' [-Wreorder]
   27 |  int par;
      |      ^~~
necklace.cpp:30:2: warning:   when initialized here [-Wreorder]
   30 |  Trie(int par = -1, int l = 0, char pchar = 0, int s_pos = 0) : pchar(pchar), par(par), len(l), s_pos(s_pos) {
      |  ^~~~
necklace.cpp:27:6: warning: 'Trie::par' will be initialized after [-Wreorder]
   27 |  int par;
      |      ^~~
necklace.cpp:24:6: warning:   'int Trie::len' [-Wreorder]
   24 |  int len;
      |      ^~~
necklace.cpp:30:2: warning:   when initialized here [-Wreorder]
   30 |  Trie(int par = -1, int l = 0, char pchar = 0, int s_pos = 0) : pchar(pchar), par(par), len(l), s_pos(s_pos) {
      |  ^~~~
necklace.cpp: In member function 'void Trie::build()':
necklace.cpp:50:44: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |   else prv = tries[tries[par]->prv]->trans[pchar];
      |                                            ^~~~~
necklace.cpp: In member function 'int Trie::ins(char, int)':
necklace.cpp:56:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   56 |   if (trans[c] == 0) trans[c] = (new Trie(arr_pos, len+1, c, p))->arr_pos;
      |             ^
necklace.cpp:56:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   56 |   if (trans[c] == 0) trans[c] = (new Trie(arr_pos, len+1, c, p))->arr_pos;
      |                            ^
necklace.cpp:57:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   57 |   return trans[c];
      |                ^
necklace.cpp: In function 'int make_match(pii&)':
necklace.cpp:106:1: warning: control reaches end of non-void function [-Wreturn-type]
  106 | }
      | ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 3 ms 668 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 3 ms 972 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 3 ms 668 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 3 ms 972 KB Output is correct
6 Correct 14 ms 2108 KB Output is correct
7 Correct 29 ms 4436 KB Output is correct
8 Correct 95 ms 10664 KB Output is correct
9 Correct 163 ms 10520 KB Output is correct
10 Correct 253 ms 12160 KB Output is correct
11 Correct 305 ms 12120 KB Output is correct
12 Correct 138 ms 9684 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 3 ms 668 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 3 ms 972 KB Output is correct
6 Correct 14 ms 2108 KB Output is correct
7 Correct 29 ms 4436 KB Output is correct
8 Correct 95 ms 10664 KB Output is correct
9 Correct 163 ms 10520 KB Output is correct
10 Correct 253 ms 12160 KB Output is correct
11 Correct 305 ms 12120 KB Output is correct
12 Correct 138 ms 9684 KB Output is correct
13 Correct 603 ms 290056 KB Output is correct
14 Partially correct 541 ms 234904 KB Output is partially correct
15 Correct 938 ms 576212 KB Output is correct
16 Partially correct 1307 ms 628740 KB Output is partially correct
17 Partially correct 1436 ms 653292 KB Output is partially correct
18 Execution timed out 1552 ms 680976 KB Time limit exceeded
19 Halted 0 ms 0 KB -