oj.uz

Submission #661016

# Submission time Handle Problem Language Result Execution time Memory
661016 2022-11-23T21:06:42 Z GusterGoose27 Necklace (Subtask 1-3) (BOI19_necklace1) C++11
45 / 85
 1028 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];

bool works(int cur, pii &p) {
	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;
	}
	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();
	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];
      |                ^
necklace.cpp: In function 'int make_match(pii&)':
necklace.cpp:100:1: warning: control reaches end of non-void function [-Wreturn-type]
  100 | }
      | ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 3 ms 976 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 3 ms 1492 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 3 ms 976 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 3 ms 1492 KB Output is correct
6 Correct 11 ms 3412 KB Output is correct
7 Correct 18 ms 7236 KB Output is correct
8 Correct 69 ms 17808 KB Output is correct
9 Correct 104 ms 17492 KB Output is correct
10 Correct 130 ms 20344 KB Output is correct
11 Correct 141 ms 20264 KB Output is correct
12 Correct 102 ms 16360 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 Correct 1 ms 724 KB Output is correct
3 Correct 3 ms 976 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 3 ms 1492 KB Output is correct
6 Correct 11 ms 3412 KB Output is correct
7 Correct 18 ms 7236 KB Output is correct
8 Correct 69 ms 17808 KB Output is correct
9 Correct 104 ms 17492 KB Output is correct
10 Correct 130 ms 20344 KB Output is correct
11 Correct 141 ms 20264 KB Output is correct
12 Correct 102 ms 16360 KB Output is correct
13 Correct 577 ms 490504 KB Output is correct
14 Partially correct 611 ms 397476 KB Output is partially correct
15 Correct 1028 ms 974896 KB Output is correct
16 Runtime error 816 ms 1048576 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -