oj.uz

Submission #661015

# Submission time Handle Problem Language Result Execution time Memory
661015 2022-11-23T20:54:39 Z GusterGoose27 Necklace (Subtask 1-3) (BOI19_necklace1) C++11
9 / 85
 1163 ms 1048576 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;
Trie *to_build[MAX_s];
int s = 0, e = 0;

class Trie {
public:
	Trie *trans[26];
	int len;
	Trie *prv = nullptr;
	Trie *par;
	char pchar;
	int s_pos;
	Trie(Trie *par = nullptr, 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, rt);
	}
	void build() {
		s++;
		for (int i = 0; i < 26; i++) {
			if (trans[i] != rt) {
				to_build[e++] = trans[i];
			}
		}
		if (len == 0) {
			return;
		}
		if (par->prv == nullptr) {
			prv = rt;
		}
		else prv = par->prv->trans[pchar];
		for (int i = 0; i < 26; i++) {
			if (trans[i] == rt) trans[i] = prv->trans[i];
		}
	}
	Trie* ins(char c, int p) {
		if (trans[c] == rt) trans[c] = new Trie(this, len+1, c, p);
		return trans[c];
	}
};

char cur_match[2*MAXN];

int make_match(pii &p) {
	int mn = 0;
	int mx = m+1;
	while (mn+1 < mx) {
		int cur = (mn+mx)/2;
		bool found = 0;
		for (int i = 0; i <= m-cur; i++) {
			Trie *pos = rt;
			for (int j = i; j < i+cur; j++) {
				pos = pos->trans[s2[j]-'a'];
				if (pos->len == cur) {
					p.first = pos->s_pos;
					p.second = i;
					found = 1;
					break;
				}
			}
			if (!found) {
				for (int j = i; j < i+cur-1; j++) {
					pos = pos->trans[s2[j]-'a'];
					if (pos->len == cur) {
						p.first = pos->s_pos;
						p.second = i;
						found = 1;
						break;
					}
				}
			}
			if (found) break;
		}
		if (found) mn = cur;
		else mx = cur;
	}
	return mn;
}


int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> s1 >> s2;
	swap(s1, s2);
	n = s1.size();
	m = s2.size();
	to_build[e++] = new Trie();
	for (int i = 0; i < n; i++) {
		Trie *cur = rt;
		for (int j = i; j < n; j++) {
			cur = cur->ins(s1[j]-'a', i);
		}
	}
	while (s < e) 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(Trie*, int, char, int)':
necklace.cpp:25:7: warning: 'Trie::pchar' will be initialized after [-Wreorder]
   25 |  char pchar;
      |       ^~~~~
necklace.cpp:24:8: warning:   'Trie* Trie::par' [-Wreorder]
   24 |  Trie *par;
      |        ^~~
necklace.cpp:27:2: warning:   when initialized here [-Wreorder]
   27 |  Trie(Trie *par = nullptr, int l = 0, char pchar = 0, int s_pos = 0) : pchar(pchar), par(par), len(l), s_pos(s_pos) {
      |  ^~~~
necklace.cpp:24:8: warning: 'Trie::par' will be initialized after [-Wreorder]
   24 |  Trie *par;
      |        ^~~
necklace.cpp:22:6: warning:   'int Trie::len' [-Wreorder]
   22 |  int len;
      |      ^~~
necklace.cpp:27:2: warning:   when initialized here [-Wreorder]
   27 |  Trie(Trie *par = nullptr, 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:44:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   44 |   else prv = par->prv->trans[pchar];
      |                              ^~~~~
necklace.cpp: In member function 'Trie* Trie::ins(char, int)':
necklace.cpp:50:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |   if (trans[c] == rt) trans[c] = new Trie(this, len+1, c, p);
      |             ^
necklace.cpp:50:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |   if (trans[c] == rt) trans[c] = new Trie(this, len+1, c, p);
      |                             ^
necklace.cpp:51:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   51 |   return trans[c];
      |                ^

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Partially correct 1 ms 720 KB Output is partially correct
3 Correct 1 ms 1364 KB Output is correct
4 Partially correct 1 ms 980 KB Output is partially correct
5 Correct 2 ms 1492 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Partially correct 1 ms 720 KB Output is partially correct
3 Correct 1 ms 1364 KB Output is correct
4 Partially correct 1 ms 980 KB Output is partially correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 6 ms 6484 KB Output is correct
7 Partially correct 10 ms 9684 KB Output is partially correct
8 Correct 13 ms 12700 KB Output is correct
9 Partially correct 16 ms 18260 KB Output is partially correct
10 Partially correct 19 ms 20308 KB Output is partially correct
11 Partially correct 19 ms 20180 KB Output is partially correct
12 Correct 20 ms 16212 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 Partially correct 1 ms 720 KB Output is partially correct
3 Correct 1 ms 1364 KB Output is correct
4 Partially correct 1 ms 980 KB Output is partially correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 6 ms 6484 KB Output is correct
7 Partially correct 10 ms 9684 KB Output is partially correct
8 Correct 13 ms 12700 KB Output is correct
9 Partially correct 16 ms 18260 KB Output is partially correct
10 Partially correct 19 ms 20308 KB Output is partially correct
11 Partially correct 19 ms 20180 KB Output is partially correct
12 Correct 20 ms 16212 KB Output is correct
13 Correct 414 ms 344408 KB Output is correct
14 Partially correct 559 ms 309692 KB Output is partially correct
15 Correct 938 ms 1012556 KB Output is correct
16 Correct 1163 ms 1039692 KB Output is correct
17 Runtime error 617 ms 1048576 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -