oj.uz

답안 #880856

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
880856 2023-11-30T07:19:45 Z vjudge1 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
5 / 85
 1500 ms 287260 KB 
// 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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 84 ms 20396 KB Output is partially correct
2 Partially correct 74 ms 20148 KB Output is partially correct
3 Partially correct 77 ms 34156 KB Output is partially correct
4 Partially correct 76 ms 36616 KB Output is partially correct
5 Partially correct 71 ms 46668 KB Output is partially correct

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 84 ms 20396 KB Output is partially correct
2 Partially correct 74 ms 20148 KB Output is partially correct
3 Partially correct 77 ms 34156 KB Output is partially correct
4 Partially correct 76 ms 36616 KB Output is partially correct
5 Partially correct 71 ms 46668 KB Output is partially correct
6 Execution timed out 1540 ms 287260 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 84 ms 20396 KB Output is partially correct
2 Partially correct 74 ms 20148 KB Output is partially correct
3 Partially correct 77 ms 34156 KB Output is partially correct
4 Partially correct 76 ms 36616 KB Output is partially correct
5 Partially correct 71 ms 46668 KB Output is partially correct
6 Execution timed out 1540 ms 287260 KB Time limit exceeded
7 Halted 0 ms 0 KB -