제출 #1081190

#제출 시각아이디문제언어결과실행 시간메모리
1081190Joshua_AnderssonNecklace (Subtask 1-3) (BOI19_necklace1)C++14
5 / 85
1601 ms1624 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll const int inf = int(1e18); typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> p2; #define rep(i, high) for (int i = 0; i < high; i++) #define repp(i, low, high) for (int i = low; i < high; i++) #define repe(i, container) for (auto& i : container) #define sz(container) ((int)container.size()) #define all(x) begin(x),end(x) inline void fast() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); } #if _LOCAL #define assert(x) if (!(x)) __debugbreak() #endif pair<int,p2> best(string a, string b, bool rev) { int ret = -1; p2 r = p2(-1, -1); vvi lcp(sz(a), vi(sz(b))); rep(starta, sz(a)) { rep(startb, sz(b)) { int rp = 0; rep(rlen, 1000) { int i = starta - rlen; int j = startb; if (i<0) break; bool good = 1; rep(k, rlen) { if (i >= sz(a) || j >= sz(b)) { good = 0; break; } good &= a[i] == b[j]; i++; j++; } if (good) rp = rlen; else break; } int lp = 0; rep(llen, 1000) { int i = starta; int j = startb - llen; if (j < 0) break; bool good = 1; rep(k, llen) { if (i >= sz(a) || j >= sz(b)) { good = 0; break; } good &= a[i] == b[j]; i++; j++; } if (good) lp = llen; } if (rp+lp>ret) { //assert(rp + lp != 84); r = { starta-rp,startb-lp }; if (rev) r.second = sz(b) - r.second - rp-lp; ret = rp+lp; } } } return { ret, r }; } signed main() { fast(); string a, b; cin >> a >> b; pair<int, p2> ans = { -1000,p2(0,0) }; ans = max(ans, best(a, b, 0)); reverse(all(b)); ans = max(ans, best(a, b, 1)); cout << ans.first << "\n" << ans.second.first << " " << ans.second.second; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...