oj.uz

Submission #862384

# Submission time Handle Problem Language Result Execution time Memory
862384 2023-10-18T07:36:09 Z maks007 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
9 / 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;
	};
	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);
	};
	cin >> a >> b;
	// 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 lambda function:
necklace.cpp:32:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   if(sz > a.size()) return make_pair(-1,-1);
      |      ~~~^~~~~~~~~~
necklace.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i = sz; i < a.size(); i ++) {
      |                   ~~^~~~~~~~~~

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Partially correct 9 ms 348 KB Output is partially correct
3 Correct 8 ms 468 KB Output is correct
4 Partially correct 9 ms 344 KB Output is partially correct
5 Correct 10 ms 348 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Partially correct 9 ms 348 KB Output is partially correct
3 Correct 8 ms 468 KB Output is correct
4 Partially correct 9 ms 344 KB Output is partially correct
5 Correct 10 ms 348 KB Output is correct
6 Correct 367 ms 668 KB Output is correct
7 Partially correct 592 ms 652 KB Output is partially correct
8 Correct 483 ms 540 KB Output is correct
9 Partially correct 299 ms 596 KB Output is partially correct
10 Partially correct 239 ms 344 KB Output is partially correct
11 Partially correct 225 ms 564 KB Output is partially correct
12 Correct 520 ms 548 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Partially correct 9 ms 348 KB Output is partially correct
3 Correct 8 ms 468 KB Output is correct
4 Partially correct 9 ms 344 KB Output is partially correct
5 Correct 10 ms 348 KB Output is correct
6 Correct 367 ms 668 KB Output is correct
7 Partially correct 592 ms 652 KB Output is partially correct
8 Correct 483 ms 540 KB Output is correct
9 Partially correct 299 ms 596 KB Output is partially correct
10 Partially correct 239 ms 344 KB Output is partially correct
11 Partially correct 225 ms 564 KB Output is partially correct
12 Correct 520 ms 548 KB Output is correct
13 Execution timed out 1529 ms 2904 KB Time limit exceeded
14 Halted 0 ms 0 KB -