제출 #880856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
880856		vjudge1	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	5 / 85	1540 ms	287260 KiB

necklace

// in the name of God
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fast() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ff first
#define ss second
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
#define mpp make_pair
#define ppb pop_back
#define endl '\n'
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O4")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9 + 9, maxn = 1e5 + 10, inf = 1e9 + 1, lg = 25, pp = 4447, modd = 1e9 + 9;

map<vector<multiset<int>>, int> mp;
string s, t;

signed main(){
	fast();
	cin >> s >> t;
	int n = s.size(), m = t.size();	
	for(int i = 0; i < n; ++i){
		vector<multiset<int>> g;
		multiset<int> tmp; g.pb(tmp);
		g[0].insert(s[i] );
		mp[g] = i + 1;
		for(int j = i + 1; j < n; ++j){
			g.pb(tmp);
			g[0].extract(s[j - 1]);
			g[0].insert(s[j]);
			g[j - i].insert(s[j - 1]);
			g[j - i].insert(s[i]);
			g[j - i - 1].extract(s[i]);
			g[j - i - 1].insert(s[j]);
			mp[g] = i + 1;	
		}
	}
	pair<int, pair<int, int>> ans = mpp(0, mpp(0, 0));
	for(int i = 0; i < m; ++i){
		vector<multiset<int>> g;
		multiset<int> tmp; g.pb(tmp);
		g[0].insert(t[i] );
		if(mp[g]){
			ans = max(ans, mpp(1LL, mpp(mp[g] - 1LL, i)));
		}
		for(int j = i + 1; j < m; ++j){
			g.pb(tmp);
			g[0].extract(t[j - 1]);
			g[0].insert(t[j]);
			g[j - i].insert(t[j - 1]);
			g[j - i].insert(t[i]);
			g[j - i - 1].extract(t[i]);
			g[j - i - 1].insert(t[j]);
			if(mp[g]){
				ans = max(ans, mpp(j - i + 1, mpp(mp[g] - 1, i)));
			}	
		}
	}
	cout << ans.ff << endl << ans.ss.ff << " " << ans.ss.ss;
}

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