oj.uz

Submission #220037

# Submission time Handle Problem Language Result Execution time Memory
220037 2020-04-06T20:52:52 Z galca Necklace (Subtask 1-3) (BOI19_necklace1) C++14
25 / 85
 1500 ms 14328 KB 
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <string>
#include <string.h>

using namespace std;

struct NodeInTree {
private:
	
	//NodeInTree* children[26]; 
	map<char, NodeInTree*> children;
public:
	set<int> pos;
	//int pos;
#if 0
	NodeInTree() {
		memset(children, 0, 26 * sizeof(NodeInTree*));
	}
#endif

	NodeInTree* getNext(char c, int pos) {
		NodeInTree* next = children[c];
		if (next == 0) {
			next = createNext(c, pos);
		}
		this->pos.insert(pos);
		return next;
	}

	NodeInTree* getNext(char c) {
		return children[c];
	}

	NodeInTree*  createNext(char c, int pos) {
		NodeInTree* next = new NodeInTree();
		//next->pos = pos;
		next->pos.insert(pos);
		children[c] = next;
		return next;
	}

	int getPos() {
		return *pos.begin();
	}
};

void freeTree(NodeInTree* root) {
	for (int i = 'a'; i <= 'z'; i++) {
		NodeInTree* n = root->getNext(i);
		if (n != 0) {
			freeTree(n);
			delete n;
		}
	}
}

void findLongestRing(const char* str1, const char* str2, long long& d, long long& p1, long long& p2) {
	
	//cout << "exec start " << endl;

	NodeInTree* stree = new NodeInTree();
	int len = strlen(str1);

	for (int i = 0; i < len; i++) {				// loop over the suffix start
		//cout << "string 1 from pos " << i << endl;
		NodeInTree* tmp = stree;

		//cout << "inserting suffix from pos " << i + 1 << endl;
		for (int k = i; k < len; k++) {	// loop over the suffix
#if 0
			// insert also "wrap around" suffixes
			for (int m = 0; m < i; m++) {
				NodeInTree* t = tmp;
				for (int l = m; l < i; l++) {
					//cout << "adding char at pos " << l << " for suffix " << i << endl;
					t = t->getNext(str1[l], m);
				}
			}
#endif		
			tmp = tmp->getNext(str1[k], i);
		}
	}

	// insert str2
	len = strlen(str2);

	long long best = 0;
	long long bestpos1, bestpos2;

	map<int, int> distances[3000];

	for (int i = len-1; i >= 0; i--) {		// go over suffixes in reverse order												//cout << "string 1 from pos " << i << endl;
		NodeInTree* tmp = stree;
		/* no optimization
		if ((len - i) <= best) {
			break;
		}
		*/

		int k;

		int mybest = 0;
		for (k = i; k < len; k++) {	// loop over the suffix
			NodeInTree* next = tmp->getNext(str2[k]);
			if (next == 0) {
				break;
			}
#if 1
			for (set<int>::iterator itr = next->pos.begin(); itr != next->pos.end(); itr++) {
				if (distances[i].find(*itr) != distances[i].end()) {
					++distances[i][*itr];
				}
				else {
					distances[i][*itr] = 1;
				}
			}
#endif
			tmp = next;
		}
		if ((k - i) > best) { 
			best = k - i;
			bestpos1 = tmp->getPos();
			bestpos2 = i;
			//cout << "updating best match for pos " << i << endl;
			//cout << "now " << best << endl;
			//cout << "string 1 pos " << bestpos1 << endl;
		}
	}
	int len1 = strlen(str1);
	int len2 = strlen(str2);
	for (int i = 0; i < len2; i++) {
		for (map<int, int>::iterator itr = distances[i].begin(); itr != distances[i].end(); itr++) {
			int pos1 = i;
			int pos2 = (*itr).first;
			int d1 = (*itr).second;
			int pos3 = pos1 + d1;

			if (pos3 < len2) {
				for (map<int, int>::iterator itr2 = distances[pos3].begin(); itr2 != distances[pos3].end(); itr2++) {
					int pos4 = (*itr2).first;
					if (pos4 < pos2) {
						int d2 = (*itr2).second;
						if (pos4 + d2 >= pos2) {
							int total_len = pos2 - pos4 + d1;
							if (total_len > best) {
								best = total_len;
								bestpos2 = pos1;
								bestpos1 = pos4;
							}
						}
					}
				}
			}
		}
	}

	for (int i = 0; i < len2; i++) {
		distances[i].erase(distances[i].begin(), distances[i].end());
	}

	for (int i = len-1; i >= 0; i--) {				// loop over the suffix start												//cout << "string 1 from pos " << i << endl;
		NodeInTree* tmp = stree;
		/* no opt
		if ((len - i) <= best) {
			break;
		}*/

		int k;
		for (k = i; k < len; k++) {	// loop over the suffix
			NodeInTree* next = tmp->getNext(str2[len - k - 1]);
			if (next == 0) {
				break;
			}
#if 1
			for (set<int>::iterator itr = next->pos.begin(); itr != next->pos.end(); itr++) {
				if (distances[i].find(*itr) != distances[i].end()) {
					++distances[i][*itr];
				}
				else {
					distances[i][*itr] = 1;
				}
			}
#endif
			tmp = next;
		}
		if ((k - i) > best) {
			best = k - i;
			bestpos1 = tmp->getPos();
			bestpos2 = len - k;

			//cout << "updating best match for inverse pos " << i << endl;
			//cout << "now " << best << endl;
			//cout << "string 1 pos " << bestpos1 << endl;
		}
	}

	for (int i = 0; i < len2; i++) {
		for (map<int, int>::iterator itr = distances[i].begin(); itr != distances[i].end(); itr++) {
			
			int pos2 = (*itr).first;
			int d1 = (*itr).second;
			int pos3 = i + d1;

			if (pos3 < len2) {
				for (map<int, int>::iterator itr2 = distances[pos3].begin(); itr2 != distances[pos3].end(); itr2++) {
					int pos4 = (*itr2).first;
					if (pos4 < pos2) {
						int d2 = (*itr2).second;
						if (pos4 + d2 >= pos2) {
							int total_len = pos2 - pos4 + d1;
							if (total_len > best) {
								best = total_len;
								bestpos2 = len - (i + total_len);
								bestpos1 = pos4;
								//cout << "updating len to " << total_len << endl;
								//cout << "i " << i << " d1 " << d1 << " pos2 " << pos2 << " pos4 " << pos4 << " d2 " << d2 << endl;
								//cout << "str2 len is " << len << endl;
							}
						}
					}
				}
			}
		}
	}
	/*
	for (int i = 0; i < len2; i++) {
		distances[i].erase(distances[i].begin(), distances[i].end());
	}*/

	d = best;
	p1 = bestpos1;
	p2 = bestpos2;

	//freeTree(stree);
}

int main() {
	string str1, str2;

	cin >> str1;
	cin >> str2;

	long long d1, d2, p11, p12, p21, p22;


#if 1
	if (str1.length() > str2.length()) {
		findLongestRing(str1.c_str(), str2.c_str(), d1, p11, p12);
	}
	else {
		findLongestRing(str2.c_str(), str1.c_str(), d1, p12, p11);
	}
#endif

	cout << d1 << endl;
	cout << p11 << " " << p12 << endl;

#if 0
	for (int i = p11; i < p11 + d1; i++) {
		cout << str1[i];
	}
	cout << endl;
	for (int i = p12; i < p12 + d1; i++) {
		cout << str2[i];
	}
	cout << endl;
#endif
	return 0;
}

Compilation message

necklace.cpp: In function 'void findLongestRing(const char*, const char*, long long int&, long long int&, long long int&)':
necklace.cpp:106:7: warning: unused variable 'mybest' [-Wunused-variable]
   int mybest = 0;
       ^~~~~~
necklace.cpp:133:6: warning: unused variable 'len1' [-Wunused-variable]
  int len1 = strlen(str1);
      ^~~~
necklace.cpp: In function 'int main()':
necklace.cpp:247:16: warning: unused variable 'd2' [-Wunused-variable]
  long long d1, d2, p11, p12, p21, p22;
                ^~
necklace.cpp:247:30: warning: unused variable 'p21' [-Wunused-variable]
  long long d1, d2, p11, p12, p21, p22;
                              ^~~
necklace.cpp:247:35: warning: unused variable 'p22' [-Wunused-variable]
  long long d1, d2, p11, p12, p21, p22;
                                   ^~~
necklace.cpp: In function 'void findLongestRing(const char*, const char*, long long int&, long long int&, long long int&)':
necklace.cpp:236:5: warning: 'bestpos2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  p2 = bestpos2;
  ~~~^~~~~~~~~~
necklace.cpp:235:5: warning: 'bestpos1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  p1 = bestpos1;
  ~~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1280 KB Output is correct
2 Correct 12 ms 1152 KB Output is correct
3 Correct 13 ms 1664 KB Output is correct
4 Correct 8 ms 1536 KB Output is correct
5 Correct 6 ms 1664 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1280 KB Output is correct
2 Correct 12 ms 1152 KB Output is correct
3 Correct 13 ms 1664 KB Output is correct
4 Correct 8 ms 1536 KB Output is correct
5 Correct 6 ms 1664 KB Output is correct
6 Execution timed out 1594 ms 14328 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1280 KB Output is correct
2 Correct 12 ms 1152 KB Output is correct
3 Correct 13 ms 1664 KB Output is correct
4 Correct 8 ms 1536 KB Output is correct
5 Correct 6 ms 1664 KB Output is correct
6 Execution timed out 1594 ms 14328 KB Time limit exceeded
7 Halted 0 ms 0 KB -