Submission #661016

#	Time	Username	Problem	Language	Result	Execution time	Memory
661016		GusterGoose27	Necklace (Subtask 1-3) (BOI19_necklace1)	C++11	45 / 85	1028 ms	1048576 KiB

necklace

#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 (stderr)

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 / 25
• Subtask 2: 20 / 20
• Subtask 3: 0 / 40