oj.uz

답안 #862387

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862387 2023-10-18T07:39:34 Z maks007 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
29 / 85
 1500 ms 2908 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;
	reverse(b.begin(), b.end());
	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;
	}
	if(l > mx) {
		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 112 ms 348 KB Output is correct
2 Correct 113 ms 488 KB Output is correct
3 Correct 65 ms 344 KB Output is correct
4 Correct 106 ms 500 KB Output is correct
5 Correct 90 ms 600 KB Output is correct

Subtask #2
4.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 348 KB Output is correct
2 Correct 113 ms 488 KB Output is correct
3 Correct 65 ms 344 KB Output is correct
4 Correct 106 ms 500 KB Output is correct
5 Correct 90 ms 600 KB Output is correct
6 Correct 445 ms 600 KB Output is correct
7 Partially correct 645 ms 856 KB Output is partially correct
8 Correct 475 ms 536 KB Output is correct
9 Partially correct 294 ms 548 KB Output is partially correct
10 Partially correct 238 ms 596 KB Output is partially correct
11 Partially correct 209 ms 348 KB Output is partially correct
12 Correct 553 ms 548 KB Output is correct

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 348 KB Output is correct
2 Correct 113 ms 488 KB Output is correct
3 Correct 65 ms 344 KB Output is correct
4 Correct 106 ms 500 KB Output is correct
5 Correct 90 ms 600 KB Output is correct
6 Correct 445 ms 600 KB Output is correct
7 Partially correct 645 ms 856 KB Output is partially correct
8 Correct 475 ms 536 KB Output is correct
9 Partially correct 294 ms 548 KB Output is partially correct
10 Partially correct 238 ms 596 KB Output is partially correct
11 Partially correct 209 ms 348 KB Output is partially correct
12 Correct 553 ms 548 KB Output is correct
13 Execution timed out 1545 ms 2908 KB Time limit exceeded
14 Halted 0 ms 0 KB -