oj.uz

답안 #862388

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862388 2023-10-18T07:41:11 Z maks007 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
29 / 85
 1500 ms 2904 KB 
#include "bits/stdc++.h"

using namespace std;

signed main () {
	string a, b;
	function <int(queue <char>)> get=[&](queue <char> str) {
		queue <char> ttr;
		int k = str.size();
		set <queue <char>> shift;
		int cnt = str.size();
		while(cnt --) {
			shift.insert(str);
			str.push(str.front());
			str.pop();
		}
		for(int i = 0; i < k; i ++) ttr.push(b[i]);
		for(int i = k; i < b.size(); i ++) {
			if(shift.count(ttr)) {
				return i-k;
			}
			ttr.pop();
			ttr.push(b[i]);
		}
		if(shift.count(ttr)) {
			return (int)b.size()-k;
		}
		return -1;
	};
	cin >> a >> b;
	if(a.size() <= 100 && b.size() <= 100) {
		int mx = -1, grana, granb;
		for(int l = 0; l < a.size(); l ++) {
			queue <char> str;
			for(int r = l; r < a.size(); r ++) {
				str.push(a[r]);
				int temp = get(str);
				if(temp == -1) continue;
				// cout << l << " " <</ r << " " << temp << "\n";
				if(temp != -1) {
					if(r-l+1 > mx) {
						mx = r-l+1;
						grana = l;
						granb = temp;
					}
				}
			}
		}
		reverse(b.begin(), b.end());
		for(int l = 0; l < a.size(); l ++) {
			queue <char> str;
			for(int r = l; r < a.size(); r ++) {
				str.push(a[r]);
				int temp = get(str);
				if(temp == -1) continue;
				// cout << l << " " << r << " " << temp << "\n";
				if(temp != -1) {
					if(r-l+1 > mx) {
						mx = r-l+1;
						granb = b.size() - (temp+(r-l+1));
						grana = l;
					}
				}
			}
		}
		cout << mx << "\n" << grana << " " << granb;
		return 0;
	}
	function<pair <int,int>(int)> good=[&](int sz) {
		if(sz == 0) return make_pair(1,1);
		queue <char> str;
		if(sz > a.size()) return make_pair(-1,-1);
		for(int i = 0; i < sz; i ++) str.push(a[i]);
		for(int i = sz; i < a.size(); i ++) {
			if(get(str) != -1) {
				return make_pair(i - sz, get(str));
			}
			str.pop();
			str.push(a[i]);
		}
		if(get(str) != -1) return make_pair((int)a.size() - sz, get(str));
		return make_pair(-1,-1);
	};
	// for(int i = 0; i < min(a.size(), b.size()); i ++) {
	// 	cout << good(i).first << " " << good(i).second << "\n";
	// }
	int l = 0, r = min(a.size(), b.size());
	while(l < r) {
		int mid = (l + r + 1) / 2;
		if(good(mid).first != -1) l = mid;
		else r = mid-1;
	}
	// cout << l << " ";
	int mx = l, grana = good(l).first, granb = good(l).second;
	if(good(l).first == -1) {
		mx = 0;
		grana = granb = 0;	
	}
	reverse(b.begin(), b.end());
	l = 1, r = min(a.size(), b.size());
	while(l < r) {
		int mid = (l + r + 1) / 2;
		if(good(mid).first != -1) l = mid;
		else r = mid-1;
	}
	if(l > mx && good(l).first != -1) {
		mx = l;
		grana = good(l).first;
		granb = b.size() - (good(l).second+mx);
	}
	cout << mx << "\n" << grana << " " << granb;
	return 0;
}

Compilation message

necklace.cpp: In lambda function:
necklace.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int i = k; i < b.size(); i ++) {
      |                  ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int l = 0; l < a.size(); l ++) {
      |                  ~~^~~~~~~~~~
necklace.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    for(int r = l; r < a.size(); r ++) {
      |                   ~~^~~~~~~~~~
necklace.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int l = 0; l < a.size(); l ++) {
      |                  ~~^~~~~~~~~~
necklace.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    for(int r = l; r < a.size(); r ++) {
      |                   ~~^~~~~~~~~~
necklace.cpp: In lambda function:
necklace.cpp:72:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   if(sz > a.size()) return make_pair(-1,-1);
      |      ~~~^~~~~~~~~~
necklace.cpp:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int i = sz; i < a.size(); i ++) {
      |                   ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:66:41: warning: 'granb' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |   cout << mx << "\n" << grana << " " << granb;
      |                                         ^~~~~
necklace.cpp:66:34: warning: 'grana' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |   cout << mx << "\n" << grana << " " << granb;
      |                                  ^~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 130 ms 348 KB Output is correct
2 Correct 127 ms 348 KB Output is correct
3 Correct 76 ms 468 KB Output is correct
4 Correct 111 ms 348 KB Output is correct
5 Correct 90 ms 348 KB Output is correct

Subtask #2
4.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 130 ms 348 KB Output is correct
2 Correct 127 ms 348 KB Output is correct
3 Correct 76 ms 468 KB Output is correct
4 Correct 111 ms 348 KB Output is correct
5 Correct 90 ms 348 KB Output is correct
6 Correct 439 ms 664 KB Output is correct
7 Partially correct 667 ms 604 KB Output is partially correct
8 Correct 568 ms 348 KB Output is correct
9 Partially correct 365 ms 596 KB Output is partially correct
10 Partially correct 256 ms 348 KB Output is partially correct
11 Partially correct 226 ms 344 KB Output is partially correct
12 Correct 642 ms 544 KB Output is correct

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 130 ms 348 KB Output is correct
2 Correct 127 ms 348 KB Output is correct
3 Correct 76 ms 468 KB Output is correct
4 Correct 111 ms 348 KB Output is correct
5 Correct 90 ms 348 KB Output is correct
6 Correct 439 ms 664 KB Output is correct
7 Partially correct 667 ms 604 KB Output is partially correct
8 Correct 568 ms 348 KB Output is correct
9 Partially correct 365 ms 596 KB Output is partially correct
10 Partially correct 256 ms 348 KB Output is partially correct
11 Partially correct 226 ms 344 KB Output is partially correct
12 Correct 642 ms 544 KB Output is correct
13 Execution timed out 1541 ms 2904 KB Time limit exceeded
14 Halted 0 ms 0 KB -