oj.uz

Submission #661013

# Submission time Handle Problem Language Result Execution time Memory
661013 2022-11-23T20:50:38 Z GusterGoose27 Necklace (Subtask 1-3) (BOI19_necklace1) C++11
9 / 85
 1000 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;
	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;
	}
	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 724 KB Output is correct
2 Partially correct 1 ms 716 KB Output is partially correct
3 Correct 1 ms 972 KB Output is correct
4 Partially correct 1 ms 1236 KB Output is partially correct
5 Correct 2 ms 1544 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Partially correct 1 ms 716 KB Output is partially correct
3 Correct 1 ms 972 KB Output is correct
4 Partially correct 1 ms 1236 KB Output is partially correct
5 Correct 2 ms 1544 KB Output is correct
6 Correct 4 ms 3284 KB Output is correct
7 Partially correct 8 ms 7336 KB Output is partially correct
8 Correct 17 ms 17740 KB Output is correct
9 Partially correct 17 ms 17492 KB Output is partially correct
10 Partially correct 20 ms 20316 KB Output is partially correct
11 Partially correct 20 ms 20172 KB Output is partially correct
12 Correct 17 ms 16204 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Partially correct 1 ms 716 KB Output is partially correct
3 Correct 1 ms 972 KB Output is correct
4 Partially correct 1 ms 1236 KB Output is partially correct
5 Correct 2 ms 1544 KB Output is correct
6 Correct 4 ms 3284 KB Output is correct
7 Partially correct 8 ms 7336 KB Output is partially correct
8 Correct 17 ms 17740 KB Output is correct
9 Partially correct 17 ms 17492 KB Output is partially correct
10 Partially correct 20 ms 20316 KB Output is partially correct
11 Partially correct 20 ms 20172 KB Output is partially correct
12 Correct 17 ms 16204 KB Output is correct
13 Correct 600 ms 490508 KB Output is correct
14 Partially correct 650 ms 397492 KB Output is partially correct
15 Correct 1000 ms 974884 KB Output is correct
16 Runtime error 823 ms 1048576 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -