Submission #921055

#	Time	Username	Problem	Language	Result	Execution time	Memory
921055		shoryu386	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	25 / 85	1538 ms	920 KiB

necklace

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define MOD 1'000'000'007LL
#define MAX 200'007


main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	string a, b; cin >> a >> b;
	
	int n = a.size(), m = b.size();
	
	int ans = -1;
	int resA, resB;
	
	for (int x = 0; x < n; x++){
		for (int y = x; y < n; y++){
			
			deque<char> hmm;
			for (int z = x; z <= y; z++) hmm.push_back(a[z]);
			
			set<deque<char>> hash;
			
			hash.insert(hmm);
			for (int x = 0; x <= (int)hmm.size(); x++){
				rotate(hmm.begin(),  hmm.begin()+1, hmm.end());
				hash.insert(hmm);
			}
			
			reverse(hmm.begin(), hmm.end());
			hash.insert(hmm);
			for (int x = 0; x <= (int)hmm.size(); x++){
				rotate(hmm.begin(), hmm.begin()+1, hmm.end());
				hash.insert(hmm);
			}
			
			deque<char> cur;
			
			for (int z = 0; z <= (y-x); z++){
				cur.push_back(b[z]);
			}
			
			if (hash.count(cur)){
				if (ans < (y-x+1)){
					ans = y-x+1;
					resA = x, resB = 0;
				}
			}
			
			for (int z = 1; z+(y-x) < m; z++){
				//cur.pop_front();
				cur.pop_front(); //slow
				cur.push_back(b[z+y-x]);
				
				if (hash.count(cur)){
					if (ans < (y-x+1)){
						ans = y-x+1;
						resA = x, resB = z;
					}
				}
			}
		}
	}
	
	cout << ans << '\n';
	cout << resA << ' ' << resB;
}

Compilation message (stderr)

necklace.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main(){
      | ^~~~

• Subtask 1: 25 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40