oj.uz

답안 #220143

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
220143 2020-04-07T06:36:45 Z galca Necklace (Subtask 1-3) (BOI19_necklace1) C++14
45 / 85
 1500 ms 453880 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;
		}
		*/
		NodeInTree* next = tmp->getNext(str2[i]);
		if (next != 0) {
			for (set<int>::iterator itr = next->pos.begin(); itr != next->pos.end(); itr++) {
				distances[i][*itr] = 0;
			}
		}
		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++) {
				++distances[i][*itr];
			}
#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) {
						break;
					}
					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;
							break;
						}
					}
				}
			}
		}
	}

	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;
		NodeInTree* next = tmp->getNext(str2[i]);
		if (next != 0) {
			for (set<int>::iterator itr = next->pos.begin(); itr != next->pos.end(); itr++) {
				distances[i][*itr] = 0;
			}
		}

		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++) {
				++distances[i][*itr];
			}
#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) {
						break;
					}
					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;
							break;
						}
					}
				}
			}
		}
	}
	/*
	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, p12, p11;


#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:111: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:237:5: warning: 'bestpos2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  p2 = bestpos2;
  ~~~^~~~~~~~~~
necklace.cpp:236:5: warning: 'bestpos1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  p1 = bestpos1;
  ~~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 1280 KB Output is correct
2 Correct 12 ms 1280 KB Output is correct
3 Correct 11 ms 1664 KB Output is correct
4 Correct 9 ms 1664 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 1280 KB Output is correct
2 Correct 12 ms 1280 KB Output is correct
3 Correct 11 ms 1664 KB Output is correct
4 Correct 9 ms 1664 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct
6 Correct 1056 ms 14536 KB Output is correct
7 Correct 309 ms 13180 KB Output is correct
8 Correct 449 ms 21496 KB Output is correct
9 Correct 244 ms 22136 KB Output is correct
10 Correct 28 ms 18304 KB Output is correct
11 Correct 33 ms 18304 KB Output is correct
12 Correct 325 ms 19448 KB Output is correct

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 1280 KB Output is correct
2 Correct 12 ms 1280 KB Output is correct
3 Correct 11 ms 1664 KB Output is correct
4 Correct 9 ms 1664 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct
6 Correct 1056 ms 14536 KB Output is correct
7 Correct 309 ms 13180 KB Output is correct
8 Correct 449 ms 21496 KB Output is correct
9 Correct 244 ms 22136 KB Output is correct
10 Correct 28 ms 18304 KB Output is correct
11 Correct 33 ms 18304 KB Output is correct
12 Correct 325 ms 19448 KB Output is correct
13 Execution timed out 1621 ms 453880 KB Time limit exceeded
14 Halted 0 ms 0 KB -