oj.uz

Submission #661040

# Submission time Handle Problem Language Result Execution time Memory
661040 2022-11-24T01:19:24 Z GusterGoose27 Necklace (Subtask 1-3) (BOI19_necklace1) C++11
45 / 85
 1500 ms 680884 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#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;
			}
		}
		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;
	}
	if (!found) {
		for (int i = 0; i <= m-cur; i++) {
			int pos = 0;
			for (int j = i+cur-1; j >= i; 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;
				}
			}
			for (int j = i+cur-1; j > i; 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:31:7: warning: 'Trie::pchar' will be initialized after [-Wreorder]
   31 |  char pchar;
      |       ^~~~~
necklace.cpp:30:6: warning:   'int Trie::par' [-Wreorder]
   30 |  int par;
      |      ^~~
necklace.cpp:33:2: warning:   when initialized here [-Wreorder]
   33 |  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:30:6: warning: 'Trie::par' will be initialized after [-Wreorder]
   30 |  int par;
      |      ^~~
necklace.cpp:27:6: warning:   'int Trie::len' [-Wreorder]
   27 |  int len;
      |      ^~~
necklace.cpp:33:2: warning:   when initialized here [-Wreorder]
   33 |  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:53:44: warning: array subscript has type 'char' [-Wchar-subscripts]
   53 |   else prv = tries[tries[par]->prv]->trans[pchar];
      |                                            ^~~~~
necklace.cpp: In member function 'int Trie::ins(char, int)':
necklace.cpp:59:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |   if (trans[c] == 0) trans[c] = (new Trie(arr_pos, len+1, c, p))->arr_pos;
      |             ^
necklace.cpp:59:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |   if (trans[c] == 0) trans[c] = (new Trie(arr_pos, len+1, c, p))->arr_pos;
      |                            ^
necklace.cpp:60:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   60 |   return trans[c];
      |                ^
necklace.cpp: In function 'int make_match(pii&)':
necklace.cpp:131:1: warning: control reaches end of non-void function [-Wreturn-type]
  131 | }
      | ^

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 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 3 ms 980 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 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 12 ms 2004 KB Output is correct
7 Correct 22 ms 4572 KB Output is correct
8 Correct 88 ms 10656 KB Output is correct
9 Correct 151 ms 10528 KB Output is correct
10 Correct 245 ms 12156 KB Output is correct
11 Correct 299 ms 12116 KB Output is correct
12 Correct 136 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 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 12 ms 2004 KB Output is correct
7 Correct 22 ms 4572 KB Output is correct
8 Correct 88 ms 10656 KB Output is correct
9 Correct 151 ms 10528 KB Output is correct
10 Correct 245 ms 12156 KB Output is correct
11 Correct 299 ms 12116 KB Output is correct
12 Correct 136 ms 9684 KB Output is correct
13 Correct 543 ms 290028 KB Output is correct
14 Partially correct 579 ms 234956 KB Output is partially correct
15 Correct 939 ms 576260 KB Output is correct
16 Partially correct 1372 ms 628744 KB Output is partially correct
17 Partially correct 1447 ms 653284 KB Output is partially correct
18 Execution timed out 1517 ms 680884 KB Time limit exceeded
19 Halted 0 ms 0 KB -