oj.uz

Submission #219971

# Submission time Handle Problem Language Result Execution time Memory
219971 2020-04-06T18:32:13 Z galca Necklace (Subtask 1-3) (BOI19_necklace1) C++14
9 / 85
 1500 ms 373848 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 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[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;
		}
	}
	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 = 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:133:6: warning: unused variable 'len1' [-Wunused-variable]
  int len1 = strlen(str1);
      ^~~~
necklace.cpp: In function 'int main()':
necklace.cpp:198:16: warning: unused variable 'd2' [-Wunused-variable]
  long long d1, d2, p11, p12, p21, p22;
                ^~
necklace.cpp:198:30: warning: unused variable 'p21' [-Wunused-variable]
  long long d1, d2, p11, p12, p21, p22;
                              ^~~
necklace.cpp:198: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:187:5: warning: 'bestpos2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  p2 = bestpos2;
  ~~~^~~~~~~~~~
necklace.cpp:186: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 7 ms 896 KB Output is partially correct
2 Partially correct 5 ms 896 KB Output is partially correct
3 Partially correct 6 ms 1152 KB Output is partially correct
4 Partially correct 5 ms 1152 KB Output is partially correct
5 Correct 6 ms 1536 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 896 KB Output is partially correct
2 Partially correct 5 ms 896 KB Output is partially correct
3 Partially correct 6 ms 1152 KB Output is partially correct
4 Partially correct 5 ms 1152 KB Output is partially correct
5 Correct 6 ms 1536 KB Output is correct
6 Partially correct 177 ms 8960 KB Output is partially correct
7 Correct 19 ms 9728 KB Output is correct
8 Partially correct 60 ms 13056 KB Output is partially correct
9 Partially correct 38 ms 17272 KB Output is partially correct
10 Partially correct 22 ms 17664 KB Output is partially correct
11 Partially correct 21 ms 17664 KB Output is partially correct
12 Correct 26 ms 14720 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 896 KB Output is partially correct
2 Partially correct 5 ms 896 KB Output is partially correct
3 Partially correct 6 ms 1152 KB Output is partially correct
4 Partially correct 5 ms 1152 KB Output is partially correct
5 Correct 6 ms 1536 KB Output is correct
6 Partially correct 177 ms 8960 KB Output is partially correct
7 Correct 19 ms 9728 KB Output is correct
8 Partially correct 60 ms 13056 KB Output is partially correct
9 Partially correct 38 ms 17272 KB Output is partially correct
10 Partially correct 22 ms 17664 KB Output is partially correct
11 Partially correct 21 ms 17664 KB Output is partially correct
12 Correct 26 ms 14720 KB Output is correct
13 Execution timed out 1615 ms 373848 KB Time limit exceeded
14 Halted 0 ms 0 KB -