Submission #584260

#TimeUsernameProblemLanguageResultExecution timeMemory
584260talant117408Necklace (Subtask 1-3) (BOI19_necklace1)C++17
85 / 85
363 ms71036 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define pb push_back #define mp make_pair #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define lb lower_bound #define ub upper_bound #define sz(v) int((v).size()) #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl '\n' vector <int> z_function(string s) { int n = sz(s); vector <int> z(n); for (int i = 1, l = 0, r = 0; i < n; i++) { if (i <= r) z[i] = min (r - i + 1, z[i - l]); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++; if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; } return z; } void solve() { string s, t; cin >> s >> t; int ans = 0, inds = -1, indt = -1; vector <vector <int>> Z(sz(s), vector <int> (sz(t))), reversed_Z(sz(s), vector <int> (sz(t))); string q = s; for (int i = 0; i < sz(s); i++) { string tmp = q + '$' + t; auto res = z_function(tmp); for (int j = sz(s) + 1; j < sz(s) + sz(t) + 1; j++) Z[i][j - sz(s) - 1] = res[j]; rotate(q.begin(), q.begin() + 1, q.end()); q.back() = '#'; } for (int i = 0; i < sz(s); i++) { for (int j = 0; j < sz(t); j++) { auto r = (j + Z[i][j]) % sz(t); if (j + Z[i][j] < sz(t)) reversed_Z[i][r] = max(reversed_Z[i][r], Z[i][j]); } } for (int i = 0; i < sz(s); i++) { for (int j = 0; j < sz(t); j++) { if (Z[i][j] == 0) continue; int nxt = (i + Z[i][j]) % sz(s); if (Z[i][j] + reversed_Z[nxt][j] > ans && Z[i][j] + reversed_Z[nxt][j] <= sz(s)) { ans = Z[i][j] + reversed_Z[nxt][j]; inds = i; indt = (j - reversed_Z[nxt][j] + sz(t)) % sz(t); //~ indt = sz(t) - (indt + ans - 1) - 1; } } } q = s; reverse(all(t)); for (int i = 0; i < sz(s); i++) { fill(all(reversed_Z[i]), 0); string tmp = q + '$' + t; auto res = z_function(tmp); for (int j = sz(s) + 1; j < sz(s) + sz(t) + 1; j++) Z[i][j - sz(s) - 1] = res[j]; rotate(q.begin(), q.begin() + 1, q.end()); q.back() = '#'; } for (int i = 0; i < sz(s); i++) { for (int j = 0; j < sz(t); j++) { auto r = (j + Z[i][j]) % sz(t); if (j + Z[i][j] < sz(t)) reversed_Z[i][r] = max(reversed_Z[i][r], Z[i][j]); } } for (int i = 0; i < sz(s); i++) { for (int j = 0; j < sz(t); j++) { if (Z[i][j] == 0) continue; int nxt = (i + Z[i][j]) % sz(s); if (Z[i][j] + reversed_Z[nxt][j] > ans && Z[i][j] + reversed_Z[nxt][j] <= sz(s)) { ans = Z[i][j] + reversed_Z[nxt][j]; inds = i; indt = (j - reversed_Z[nxt][j] + sz(t)) % sz(t); indt = sz(t) - (indt + ans - 1) - 1; } } } cout << ans << endl; cout << inds << ' ' << indt << endl; } int main() { do_not_disturb int t = 1; //~ cin >> t; while (t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...