Submission #873052

#	Time	Username	Problem	Language	Result	Execution time	Memory
873052		Trisanu_Das	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	29 / 85	1558 ms	2908 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;
	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 (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: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 / 25
• Subtask 2: 4 / 20
• Subtask 3: 0 / 40