Submission #862328

#	Time	Username	Problem	Language	Result	Execution time	Memory
862328		maks007	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	25 / 85	1573 ms	852 KiB

necklace

#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 (stderr)

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 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40