oj.uz

Submission #219955

# Submission time Handle Problem Language Result Execution time Memory
219955 2020-04-06T17:57:06 Z galca Necklace (Subtask 1-3) (BOI19_necklace1) C++14
17 / 85
 575 ms 559244 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;
		children[c] = next;
		return next;
	}

	int getPos() {
		return pos;
	}
};

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:105:7: warning: unused variable 'mybest' [-Wunused-variable]
   int mybest = 0;
       ^~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:176:16: warning: unused variable 'd2' [-Wunused-variable]
  long long d1, d2, p11, p12, p21, p22;
                ^~
necklace.cpp:176:30: warning: unused variable 'p21' [-Wunused-variable]
  long long d1, d2, p11, p12, p21, p22;
                              ^~~
necklace.cpp:176: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:165:5: warning: 'bestpos2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  p2 = bestpos2;
  ~~~^~~~~~~~~~
necklace.cpp:164: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 640 KB Output is partially correct
2 Partially correct 5 ms 640 KB Output is partially correct
3 Partially correct 5 ms 768 KB Output is partially correct
4 Partially correct 5 ms 768 KB Output is partially correct
5 Partially correct 5 ms 1024 KB Output is partially correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 640 KB Output is partially correct
2 Partially correct 5 ms 640 KB Output is partially correct
3 Partially correct 5 ms 768 KB Output is partially correct
4 Partially correct 5 ms 768 KB Output is partially correct
5 Partially correct 5 ms 1024 KB Output is partially correct
6 Partially correct 9 ms 3456 KB Output is partially correct
7 Partially correct 10 ms 5120 KB Output is partially correct
8 Partially correct 12 ms 6528 KB Output is partially correct
9 Partially correct 15 ms 8832 KB Output is partially correct
10 Partially correct 15 ms 10240 KB Output is partially correct
11 Partially correct 14 ms 10112 KB Output is partially correct
12 Partially correct 13 ms 8320 KB Output is partially correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 640 KB Output is partially correct
2 Partially correct 5 ms 640 KB Output is partially correct
3 Partially correct 5 ms 768 KB Output is partially correct
4 Partially correct 5 ms 768 KB Output is partially correct
5 Partially correct 5 ms 1024 KB Output is partially correct
6 Partially correct 9 ms 3456 KB Output is partially correct
7 Partially correct 10 ms 5120 KB Output is partially correct
8 Partially correct 12 ms 6528 KB Output is partially correct
9 Partially correct 15 ms 8832 KB Output is partially correct
10 Partially correct 15 ms 10240 KB Output is partially correct
11 Partially correct 14 ms 10112 KB Output is partially correct
12 Partially correct 13 ms 8320 KB Output is partially correct
13 Partially correct 398 ms 167800 KB Output is partially correct
14 Partially correct 226 ms 150780 KB Output is partially correct
15 Partially correct 522 ms 473200 KB Output is partially correct
16 Partially correct 553 ms 504656 KB Output is partially correct
17 Partially correct 547 ms 536312 KB Output is partially correct
18 Partially correct 575 ms 559244 KB Output is partially correct
19 Partially correct 484 ms 448760 KB Output is partially correct
20 Partially correct 496 ms 443652 KB Output is partially correct
21 Partially correct 507 ms 463608 KB Output is partially correct