Submission #1254406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254406		_rain_	Necklace (Subtask 1-3) (BOI19_necklace1)	C++20	25 / 85	123 ms	440 KiB

necklace

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

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define sz(x) (int)(x).size()
#define BIT(mask , x) (((mask)>>(x))&(1))
#define MASK(x) ((LL)(1)<<(x))

template<class X,class Y>
	bool maximize(X &x, Y y){
		if (x<y) return x = y , true; else return false;
	}
template<class X,class Y>	
	bool minimize(X &x, Y y){
		if (x>y) return x = y , true; else return false;
	}
	
const int N = (int) 300;
int n,m;
string s1 , s2;
	
namespace subtask1{
	bool check(){
		return n <= 100;
	}
	
	int kmp[N+2] = {};
	int f[N+2] = {};
	int pos1 , pos2;
	
	void match_kmp(string s){
		s = '#' + s;
		kmp[1] = 0;
		for(int i = 2; i < sz(s); ++i){
			int cur = kmp[i - 1];
			while (cur && s[cur + 1] != s[i]) cur = kmp[cur];
			if (s[cur+1] == s[i]) kmp[i] = ++cur; else kmp[i] = 0;
		}
		return ;
	}	
	
	bool match(string t , string s){
		t = '#' + t + t;
		f[0] = 0;
		for(int i = 1; i < sz(t); ++i){
			int cur = f[i - 1];
			while (cur && s[cur + 1] != t[i]) cur = kmp[cur];
			if (s[cur + 1] != t[i]) f[i] = 0; else f[i] = ++cur;
			if (f[i] == s.size()-1) return true;
		}
		return false;
	}
	
	bool process(string s ,int length){
		s = '#' + s;
		for(int i = 1; i <= m - length + 1; ++i){
			string t = "";
			for(int j = i; j <= i + length - 1; ++j) t.push_back(s2[j]);
			if (match(t , s)) {
				pos2 = i;
				return true;
			}
		}
		return false;
	}
	
	bool possible(int length){
		for(int i = 1; i <= n - length + 1; ++i){
			string t = "";
			for(int j = i; j <= i + length - 1; ++j) t.push_back(s1[j]);

			match_kmp(t);
			if (process(t , length)) {
				pos1 = i;
				return true;
			}
			reverse(t.begin() , t.end());
			match_kmp(t);
			if (process(t , length)) {
				pos1 = i;
				return true;
			}
		}
		return false;
	}
	
	void main_code(){
		int low = 1 , high = n , ans = -1;
		int ans_p1 , ans_p2;
		for(int i = n; i >= 1; --i){
			if (possible(i)){
				ans = i , 
				ans_p1 = pos1 , ans_p2 = pos2;
				break;
			}
		}
		cout << ans << '\n';
		cout<<ans_p1 - 1 << ' ' << ans_p2 - 1 << '\n';
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ; 
	#define name "main"
		if (fopen(name".inp" , "r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> s1 >> s2;
		s1 = '#' + s1 , s2 = '#' + s2;
		n = sz(s1) - 1 , m = sz(s2) - 1;
		return subtask1::main_code() , 0;
}

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:108:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:109:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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