oj.uz

Submission #661039

# Submission time Handle Problem Language Result Execution time Memory
661039 2022-11-24T01:09:16 Z GusterGoose27 Necklace (Subtask 1-3) (BOI19_necklace1) C++11
45 / 85
 1500 ms 680844 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;
			}
		}
		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: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:109:1: warning: control reaches end of non-void function [-Wreturn-type]
  109 | }
      | ^

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 14 ms 2104 KB Output is correct
7 Correct 29 ms 4484 KB Output is correct
8 Correct 93 ms 10656 KB Output is correct
9 Correct 162 ms 10528 KB Output is correct
10 Correct 250 ms 12164 KB Output is correct
11 Correct 306 ms 12116 KB Output is correct
12 Correct 138 ms 9752 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 14 ms 2104 KB Output is correct
7 Correct 29 ms 4484 KB Output is correct
8 Correct 93 ms 10656 KB Output is correct
9 Correct 162 ms 10528 KB Output is correct
10 Correct 250 ms 12164 KB Output is correct
11 Correct 306 ms 12116 KB Output is correct
12 Correct 138 ms 9752 KB Output is correct
13 Correct 588 ms 290016 KB Output is correct
14 Partially correct 527 ms 235004 KB Output is partially correct
15 Correct 907 ms 576204 KB Output is correct
16 Partially correct 1271 ms 628660 KB Output is partially correct
17 Partially correct 1407 ms 653372 KB Output is partially correct
18 Execution timed out 1528 ms 680844 KB Time limit exceeded
19 Halted 0 ms 0 KB -