oj.uz

답안 #873052

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
873052 2023-11-14T11:32:46 Z Trisanu_Das Necklace (Subtask 1-3) (BOI19_necklace1) C++17
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) {
		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:71:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   if(sz > a.size()) return make_pair(-1,-1);
      |      ~~~^~~~~~~~~~
necklace.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   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 129 ms 348 KB Output is correct
2 Correct 125 ms 344 KB Output is correct
3 Correct 67 ms 348 KB Output is correct
4 Correct 113 ms 492 KB Output is correct
5 Correct 90 ms 488 KB Output is correct

Subtask #2
4.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 348 KB Output is correct
2 Correct 125 ms 344 KB Output is correct
3 Correct 67 ms 348 KB Output is correct
4 Correct 113 ms 492 KB Output is correct
5 Correct 90 ms 488 KB Output is correct
6 Correct 356 ms 856 KB Output is correct
7 Partially correct 507 ms 648 KB Output is partially correct
8 Correct 521 ms 552 KB Output is correct
9 Partially correct 318 ms 556 KB Output is partially correct
10 Partially correct 236 ms 348 KB Output is partially correct
11 Partially correct 212 ms 560 KB Output is partially correct
12 Correct 554 ms 564 KB Output is correct

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 348 KB Output is correct
2 Correct 125 ms 344 KB Output is correct
3 Correct 67 ms 348 KB Output is correct
4 Correct 113 ms 492 KB Output is correct
5 Correct 90 ms 488 KB Output is correct
6 Correct 356 ms 856 KB Output is correct
7 Partially correct 507 ms 648 KB Output is partially correct
8 Correct 521 ms 552 KB Output is correct
9 Partially correct 318 ms 556 KB Output is partially correct
10 Partially correct 236 ms 348 KB Output is partially correct
11 Partially correct 212 ms 560 KB Output is partially correct
12 Correct 554 ms 564 KB Output is correct
13 Execution timed out 1558 ms 2908 KB Time limit exceeded
14 Halted 0 ms 0 KB -