oj.uz

Submission #862328

# Submission time Handle Problem Language Result Execution time Memory
862328 2023-10-18T04:36:15 Z maks007 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
25 / 85
 1500 ms 852 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;
	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;
}

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:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(int l = 0; l < a.size(); l ++) {
      |                 ~~^~~~~~~~~~
necklace.cpp:34:20: 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 r = l; r < a.size(); r ++) {
      |                  ~~^~~~~~~~~~
necklace.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int l = 0; l < a.size(); l ++) {
      |                 ~~^~~~~~~~~~
necklace.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int r = l; r < a.size(); r ++) {
      |                  ~~^~~~~~~~~~
necklace.cpp:65:40: warning: 'granb' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |  cout << mx << "\n" << grana << " " << granb;
      |                                        ^~~~~
necklace.cpp:65:33: warning: 'grana' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |  cout << mx << "\n" << grana << " " << granb;
      |                                 ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 500 KB Output is correct
2 Correct 117 ms 492 KB Output is correct
3 Correct 63 ms 348 KB Output is correct
4 Correct 101 ms 596 KB Output is correct
5 Correct 94 ms 492 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 500 KB Output is correct
2 Correct 117 ms 492 KB Output is correct
3 Correct 63 ms 348 KB Output is correct
4 Correct 101 ms 596 KB Output is correct
5 Correct 94 ms 492 KB Output is correct
6 Execution timed out 1573 ms 852 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 500 KB Output is correct
2 Correct 117 ms 492 KB Output is correct
3 Correct 63 ms 348 KB Output is correct
4 Correct 101 ms 596 KB Output is correct
5 Correct 94 ms 492 KB Output is correct
6 Execution timed out 1573 ms 852 KB Time limit exceeded
7 Halted 0 ms 0 KB -