# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
857123 | 2023-10-05T11:59:28 Z | hgglmao | Necklace (Subtask 4) (BOI19_necklace4) | C++17 | 220 ms | 852 KB |
#include <bits/stdc++.h> #define TASK "necklace" using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef pair<int, ll> ill; typedef pair<ll, int> lli; typedef pair<ll, ll> pll; const int MAX = 6001; const int MOD = 1e9 + 7; string a, b; int na, nb; int rs, ra, rb; int k1[MAX], k2[MAX]; void KYS(string s, int *kys) { kys[0] = 0; for (int i = 1; i < s.size(); ++i) { int j = kys[i - 1]; while (j > 0 && s[i] != s[j]) j = kys[j - 1]; if (s[i] == s[j]) kys[i] = j + 1; else kys[i] = 0; } } void SOLVE(bool revb) { for (int i = 0; i < na; ++i) { string al = a.substr(0, i), ar = a.substr(i, na - i); string bl = b, br = b; reverse(al.begin(), al.end()); reverse(br.begin(), br.end()); KYS(al + "!" + bl, k1); KYS(ar + "!" + br, k2); for (int j = 1; j <= nb; ++j) if (rs < k1[i + j] + k2[na + nb - i - j]) { rs = k1[i + j] + k2[na + nb - i - j]; ra = i - k1[i + j]; if (revb) rb = nb - j - k2[na + nb - i - j]; else rb = j - k1[i + j]; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(TASK ".inp", "r")) { freopen(TASK ".inp", "r", stdin); freopen(TASK ".out", "w", stdout); } cin >> a >> b; na = a.size(), nb = b.size(); SOLVE(0); reverse(b.begin(), b.end()); SOLVE(1); cout << rs << '\n' << ra << ' ' << rb; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 200 ms | 584 KB | Output is correct |
2 | Correct | 186 ms | 604 KB | Output is correct |
3 | Correct | 220 ms | 576 KB | Output is correct |
4 | Correct | 178 ms | 576 KB | Output is correct |
5 | Correct | 117 ms | 348 KB | Output is correct |
6 | Correct | 131 ms | 852 KB | Output is correct |
7 | Correct | 154 ms | 596 KB | Output is correct |
8 | Correct | 166 ms | 344 KB | Output is correct |
9 | Correct | 172 ms | 584 KB | Output is correct |