oj.uz

Submission #219988

# Submission time Handle Problem Language Result Execution time Memory
219988 2020-04-06T18:59:24 Z galca Necklace (Subtask 1-3) (BOI19_necklace1) C++14
9 / 85
 1500 ms 451832 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[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:199:16: warning: unused variable 'd2' [-Wunused-variable]
  long long d1, d2, p11, p12, p21, p22;
                ^~
necklace.cpp:199:30: warning: unused variable 'p21' [-Wunused-variable]
  long long d1, d2, p11, p12, p21, p22;
                              ^~~
necklace.cpp:199: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:188:5: warning: 'bestpos2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  p2 = bestpos2;
  ~~~^~~~~~~~~~
necklace.cpp:187: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 14 ms 1280 KB Output is partially correct
2 Partially correct 9 ms 1152 KB Output is partially correct
3 Partially correct 8 ms 1280 KB Output is partially correct
4 Partially correct 6 ms 1280 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 14 ms 1280 KB Output is partially correct
2 Partially correct 9 ms 1152 KB Output is partially correct
3 Partially correct 8 ms 1280 KB Output is partially correct
4 Partially correct 6 ms 1280 KB Output is partially correct
5 Correct 6 ms 1536 KB Output is correct
6 Partially correct 850 ms 14240 KB Output is partially correct
7 Correct 238 ms 12836 KB Output is correct
8 Partially correct 271 ms 16888 KB Output is partially correct
9 Correct 119 ms 18424 KB Output is correct
10 Partially correct 32 ms 17912 KB Output is partially correct
11 Correct 36 ms 17912 KB Output is correct
12 Correct 240 ms 18168 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 14 ms 1280 KB Output is partially correct
2 Partially correct 9 ms 1152 KB Output is partially correct
3 Partially correct 8 ms 1280 KB Output is partially correct
4 Partially correct 6 ms 1280 KB Output is partially correct
5 Correct 6 ms 1536 KB Output is correct
6 Partially correct 850 ms 14240 KB Output is partially correct
7 Correct 238 ms 12836 KB Output is correct
8 Partially correct 271 ms 16888 KB Output is partially correct
9 Correct 119 ms 18424 KB Output is correct
10 Partially correct 32 ms 17912 KB Output is partially correct
11 Correct 36 ms 17912 KB Output is correct
12 Correct 240 ms 18168 KB Output is correct
13 Execution timed out 1621 ms 451832 KB Time limit exceeded
14 Halted 0 ms 0 KB -