//randomized: time expected O(n^3)
#pragma GCC optimize("Ofast")
#include <algorithm>
#include <chrono>
#include <ctime>
#include <iostream>
#include <random>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
mt19937 gen;
clock_t c_start;
int solve_noflip(string &a, string &b, clock_t c_end, int *loc) {
string s[2] = {a, b};
int n[2] = {a.size(), b.size()};
int l[2];
int r[2];
int res = 0;
#ifdef LOC
int cnt = 0;
ll ops = 0;
#endif
while (clock() < c_end) {
#ifdef LOC
++cnt;
#endif
for (int i = 0; i < 2; ++i) {
l[i] = gen() % n[i];
r[i] = l[i];
}
if (2 * (min(l[0], l[1]) + min(n[0] - r[0], n[1] - r[1])) <= res) continue;
while (min(l[0], l[1]) > 0 && s[0][l[0] - 1] == s[1][l[1] - 1]) {
#ifdef LOC
++ops;
#endif
--l[0];
--l[1];
}
if (2 * (r[0] - l[0] + min(n[0] - r[0], n[1] - r[1])) <= res) continue;
while (r[0] < n[0] && r[1] < n[1] && s[0][r[0]] == s[1][r[1]]) {
#ifdef LOC
++ops;
#endif
++r[0];
++r[1];
}
int len = r[0] - l[0];
if (2 * len <= res) continue;
if (len > res) {
res = len;
#ifdef LOC
fprintf(stderr, "str = %d\n", res);
fprintf(stderr, "cnt = %d\n", cnt);
fprintf(stderr, "ops = %lld\n", ops);
#endif
loc[0] = l[0];
loc[1] = l[1];
}
for (int i = 0; i < 2; ++i) {
for (int j = min(len, min(n[i] - r[i], l[!i])); j > res - len; --j) {
int tl[2];
tl[i] = r[i];
tl[!i] = l[!i] - j;
bool err = false;
for (int k = 0; k < j; ++k, ++tl[0], ++tl[1]) {
#ifdef LOC
++ops;
#endif
if (s[0][tl[0]] != s[1][tl[1]]) {
err = true;
break;
}
}
if (!err) {
res = len + j;
#ifdef LOC
fprintf(stderr, "neck = %d\n", res);
fprintf(stderr, "cnt = %d\n", cnt);
fprintf(stderr, "ops = %lld\n", ops);
#endif
loc[i] = l[i];
loc[!i] = l[!i] - j;
}
}
}
}
#ifdef LOC
fprintf(stderr, "cnt = %d\n", cnt);
fprintf(stderr, "ops = %lld\n", ops);
#endif
return res;
}
int solve(string &s, string &t, int *loc) {
int loc_noflip[2];
int res = solve_noflip(s, t, c_start + CLOCKS_PER_SEC * 48 / 100, loc_noflip);
reverse(t.begin(), t.end());
int loc_flip[2];
int res_flip = solve_noflip(s, t, c_start + CLOCKS_PER_SEC * 96 / 100, loc_flip);
if (res_flip > res) {
res = res_flip;
loc[0] = loc_flip[0];
loc[1] = (int)t.size() - loc_flip[1] - res;
} else {
for (int i = 0; i < 2; ++i) loc[i] = loc_noflip[i];
}
return res;
}
const int nmax = 3e3+5;
char buf[nmax];
int main() {
c_start = std::clock();
ll seed = static_cast< ll >(std::chrono::system_clock::now().time_since_epoch().count());
gen = mt19937(seed);
gen.discard(gen.state_size);
scanf("%s", buf);
string s(buf);
scanf("%s", buf);
string t(buf);
int loc[2];
int res = solve(s, t, loc);
cout << res << '\n';
if (res) {
cout << loc[0] << ' ' << loc[1] << '\n';
}
return 0;
}
Compilation message
necklace.cpp: In function 'int solve_noflip(std::__cxx11::string&, std::__cxx11::string&, clock_t, int*)':
necklace.cpp:21:21: warning: narrowing conversion of '(& a)->std::__cxx11::basic_string<char>::size()' from 'std::__cxx11::basic_string<char>::size_type {aka long unsigned int}' to 'int' inside { } [-Wnarrowing]
int n[2] = {a.size(), b.size()};
~~~~~~^~
necklace.cpp:21:31: warning: narrowing conversion of '(& b)->std::__cxx11::basic_string<char>::size()' from 'std::__cxx11::basic_string<char>::size_type {aka long unsigned int}' to 'int' inside { } [-Wnarrowing]
int n[2] = {a.size(), b.size()};
~~~~~~^~
necklace.cpp: In function 'int main()':
necklace.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", buf);
~~~~~^~~~~~~~~~~
necklace.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", buf);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
962 ms |
376 KB |
Output is correct |
| 2 |
Correct |
962 ms |
376 KB |
Output is correct |
| 3 |
Correct |
962 ms |
380 KB |
Output is correct |
| 4 |
Correct |
962 ms |
376 KB |
Output is correct |
| 5 |
Correct |
962 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
962 ms |
376 KB |
Output is correct |
| 2 |
Correct |
962 ms |
376 KB |
Output is correct |
| 3 |
Correct |
962 ms |
380 KB |
Output is correct |
| 4 |
Correct |
962 ms |
376 KB |
Output is correct |
| 5 |
Correct |
962 ms |
256 KB |
Output is correct |
| 6 |
Correct |
962 ms |
476 KB |
Output is correct |
| 7 |
Correct |
962 ms |
364 KB |
Output is correct |
| 8 |
Correct |
962 ms |
376 KB |
Output is correct |
| 9 |
Correct |
962 ms |
256 KB |
Output is correct |
| 10 |
Correct |
962 ms |
376 KB |
Output is correct |
| 11 |
Correct |
962 ms |
376 KB |
Output is correct |
| 12 |
Correct |
962 ms |
404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
962 ms |
376 KB |
Output is correct |
| 2 |
Correct |
962 ms |
376 KB |
Output is correct |
| 3 |
Correct |
962 ms |
380 KB |
Output is correct |
| 4 |
Correct |
962 ms |
376 KB |
Output is correct |
| 5 |
Correct |
962 ms |
256 KB |
Output is correct |
| 6 |
Correct |
962 ms |
476 KB |
Output is correct |
| 7 |
Correct |
962 ms |
364 KB |
Output is correct |
| 8 |
Correct |
962 ms |
376 KB |
Output is correct |
| 9 |
Correct |
962 ms |
256 KB |
Output is correct |
| 10 |
Correct |
962 ms |
376 KB |
Output is correct |
| 11 |
Correct |
962 ms |
376 KB |
Output is correct |
| 12 |
Correct |
962 ms |
404 KB |
Output is correct |
| 13 |
Correct |
962 ms |
376 KB |
Output is correct |
| 14 |
Correct |
962 ms |
376 KB |
Output is correct |
| 15 |
Correct |
962 ms |
476 KB |
Output is correct |
| 16 |
Correct |
962 ms |
504 KB |
Output is correct |
| 17 |
Correct |
962 ms |
376 KB |
Output is correct |
| 18 |
Partially correct |
962 ms |
476 KB |
Output is partially correct |
| 19 |
Correct |
962 ms |
412 KB |
Output is correct |
| 20 |
Correct |
962 ms |
504 KB |
Output is correct |
| 21 |
Correct |
962 ms |
376 KB |
Output is correct |
