| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 992285 | todorokishotoua1 | Necklace (Subtask 4) (BOI19_necklace4) | C++17 | 30 ms | 65536 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
// typedef tree<
// int,
// null_type,
// less_equal<int>,
// rb_tree_tag,
// tree_order_statistics_node_update
// >
// ordered_set;
namespace __gnu_pbds{
typedef tree<long long,
null_type,
less_equal<long long>,
rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
}
using namespace __gnu_pbds;
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
void __print32_t(int32_t x) {cerr << x;}
void __print32_t(long x) {cerr << x;}
void __print32_t(long long x) {cerr << x;}
void __print32_t(unsigned x) {cerr << x;}
void __print32_t(unsigned long x) {cerr << x;}
void __print32_t(unsigned long long x) {cerr << x;}
void __print32_t(float x) {cerr << x;}
void __print32_t(double x) {cerr << x;}
void __print32_t(long double x) {cerr << x;}
void __print32_t(char x) {cerr << '\'' << x << '\'';}
void __print32_t(const char *x) {cerr << '\"' << x << '\"';}
void __print32_t(const string &x) {cerr << '\"' << x << '\"';}
void __print32_t(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print32_t(const pair<T, V> &x) {cerr << '{'; __print32_t(x.first); cerr << ','; __print32_t(x.second); cerr << '}';}
template<typename T>
void __print32_t(const T &x) {int32_t f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print32_t(i); cerr << "}";}
void _print32_t() {cerr << "]\n";}
template <typename T, typename... V>
void _print32_t(T t, V... v) {__print32_t(t); if (sizeof...(v)) cerr << ", "; _print32_t(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print32_t(x)
#else
#define debug(x...)
#endif
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
#define rep(i,a,b) for(int32_t i = a; i < b; i ++)
#define ill long long int32_t
#define ll long long
#define int int64_t
#define nl "\n"
#define el endl
#define pb push_back
#define FOR(a,b,c) for (int32_t a = b; a < c; a++)
using namespace std;
// const int32_t N = 3e5+1;
const ll neg_inf = -2e7 + 2;
const ll inf = 1e18 + 1;
// const int32_t mod = 998244353;
// const int32_t MOD = 1e9+7;
const int32_t MAXN = 4e6+1;
const int32_t eps = 1e-6;
const int N = 2e5+1;
array<int,3> solve (string s, string t) {
string fin = s;
fin += '#';
fin += t;
int n = fin.size();
vector<vector<int>> d1(s.size(),vector<int>(t.size(),0));
for (int l = 0; l < s.size(); l++) {
vector<int> pi(n,0);
for (int i = 1; i < fin.size(); i++) {
int j = pi[i-1];
while (j > 0 && fin[j]!=fin[i]) j=pi[j-1];
pi[i] = j+(fin[i]==fin[j]);
}
for (int i = s.size()+1; i < n; i++) {
d1[l][i-s.size()-1] = pi[i-l];
}
// debug(l,pi,fin);
fin.erase(fin.begin());
}
// debug(d1);
string fin2 = t;
fin2 += '#';
fin2 += s;
n = fin2.size();
vector<vector<int>> d2(s.size(),vector<int>(t.size(),0));
for (int l = 0; l < t.size(); l++) {
vector<int> pi(n,0);
for (int i = 1; i < fin2.size(); i++) {
int j = pi[i-1];
while (j > 0 && fin2[i]!=fin2[j]) j=pi[j-1];
pi[i] = (j)+(fin2[i]==fin2[j]);
}
for (int i = t.size()+1; i < n; i++) {
d2[i-t.size()-1][l] = pi[i-l];
}
// debug(l,pi,fin2);
fin2.erase(fin2.begin());
}
// debug(d2);
int ans = 0;
int st1 = 0, st2 = 0;
for (int i = 0; i < s.size(); i++) {
for (int j = 0; j < t.size(); j++) {
int currans = d1[i][j];
if (i-1 >= 0 && j+1 < t.size()) {
currans += d2[i-1][j+1];
}
if (currans > ans) {
ans = currans;
int torem1 = i;
int torem2 = j+1-d1[i][j];
if (i-1 >= 0 && j+1 < t.size()) {
torem1 -= d2[i-1][j+1];
}
st1 = torem1;
st2 = torem2;
}
}
}
return {ans,st1,st2};
}
ll runcases()
{
string s,t;
cin >> s >> t;
// debug(s,t);
auto ans1 = solve(s,t);
// debug(s,t,ans1);
reverse(t.begin(),t.end());
auto ans2 = solve(s,t);
// debug(ans2);
if (ans1[0] > ans2[0]) {
cout << ans1[0] << nl << ans1[1] << " " << ans1[2];
}
else {
cout << ans2[0] << nl << ans2[1] << " " << t.size()-(ans2[0]+ans2[2]);
}
return 0;
}
signed main()
{
//..........Fast I/O.........//
// ios_base::sync_with_stdio(false);
// cin.tie(0);cout.tie(0);
//..........................//
ll t ;
t = 1;
// debug(t);
for (int32_t i = 1; i <= t; i ++) {
runcases();
}
return 0;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||