oj.uz

Submission #219956

# Submission time Handle Problem Language Result Execution time Memory
219956 2020-04-06T18:00:22 Z galca Necklace (Subtask 1-3) (BOI19_necklace1) C++14
17 / 85
 911 ms 977960 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);
		}
	
		return next;
	}

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

	NodeInTree*  createNext(char c, int pos) {
		NodeInTree* next = new NodeInTree();
		//this->pos = pos;
		this->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 0
			++mybest;
			for (set<int>::iterator itr = next->pos.begin(); itr != next->pos.end(); itr++) {
				if (distances[i].find(*itr) != distances[i].end()) {
					++distances[i][*itr];
					if (distances[k + 1][*itr - (k - i)] != 0) {

					}
				}
				else {
					distances[k][*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;
		}
	}

	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;
			}
			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;
		}
	}

	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;

	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: In function 'int main()':
necklace.cpp:177:16: warning: unused variable 'd2' [-Wunused-variable]
  long long d1, d2, p11, p12, p21, p22;
                ^~
necklace.cpp:177:30: warning: unused variable 'p21' [-Wunused-variable]
  long long d1, d2, p11, p12, p21, p22;
                              ^~~
necklace.cpp:177: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:166:5: warning: 'bestpos2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  p2 = bestpos2;
  ~~~^~~~~~~~~~
necklace.cpp:165:5: warning: 'bestpos1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  p1 = bestpos1;
  ~~~^~~~~~~~~~

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 768 KB Output is partially correct
2 Partially correct 5 ms 768 KB Output is partially correct
3 Partially correct 5 ms 1024 KB Output is partially correct
4 Partially correct 5 ms 1152 KB Output is partially correct
5 Partially correct 6 ms 1536 KB Output is partially correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 768 KB Output is partially correct
2 Partially correct 5 ms 768 KB Output is partially correct
3 Partially correct 5 ms 1024 KB Output is partially correct
4 Partially correct 5 ms 1152 KB Output is partially correct
5 Partially correct 6 ms 1536 KB Output is partially correct
6 Partially correct 12 ms 5760 KB Output is partially correct
7 Partially correct 13 ms 8448 KB Output is partially correct
8 Partially correct 15 ms 11136 KB Output is partially correct
9 Partially correct 19 ms 15104 KB Output is partially correct
10 Partially correct 23 ms 17528 KB Output is partially correct
11 Partially correct 20 ms 17408 KB Output is partially correct
12 Partially correct 18 ms 14080 KB Output is partially correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 768 KB Output is partially correct
2 Partially correct 5 ms 768 KB Output is partially correct
3 Partially correct 5 ms 1024 KB Output is partially correct
4 Partially correct 5 ms 1152 KB Output is partially correct
5 Partially correct 6 ms 1536 KB Output is partially correct
6 Partially correct 12 ms 5760 KB Output is partially correct
7 Partially correct 13 ms 8448 KB Output is partially correct
8 Partially correct 15 ms 11136 KB Output is partially correct
9 Partially correct 19 ms 15104 KB Output is partially correct
10 Partially correct 23 ms 17528 KB Output is partially correct
11 Partially correct 20 ms 17408 KB Output is partially correct
12 Partially correct 18 ms 14080 KB Output is partially correct
13 Partially correct 511 ms 292580 KB Output is partially correct
14 Partially correct 341 ms 263288 KB Output is partially correct
15 Partially correct 805 ms 827548 KB Output is partially correct
16 Partially correct 855 ms 882936 KB Output is partially correct
17 Partially correct 898 ms 938048 KB Output is partially correct
18 Partially correct 911 ms 977960 KB Output is partially correct
19 Partially correct 775 ms 784792 KB Output is partially correct
20 Partially correct 761 ms 775672 KB Output is partially correct
21 Partially correct 798 ms 810872 KB Output is partially correct