oj.uz

Submission #460416

# Submission time Handle Problem Language Result Execution time Memory
460416 2021-08-09T06:32:42 Z bonopo Necklace (Subtask 1-3) (BOI19_necklace1) C++14
85 / 85
 290 ms 580 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define rc (i<<1)|1
#define lc (i<<1)
#define el "\n"
#define f first
#define s second

typedef long long ll;
const int MM=2e5+5, MOD=1e9+7, LOG=19;
pair<int,pair<int,int>> ans;
string s, t;

vector<int> lps(string k) {
    int m=k.size(), i=1, len=0;
    vector<int> ret(m+1);
    while(i<m) {
        if(k[i]==k[len]) ret[i++]=++len;
        else if(len) len=ret[len-1];
        else ret[i++]=0; }
    return ret;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>s>>t;
    for(int r=0, N=s.size(), M=t.size(); r<2; ++r) {
        for(int i=0; i<N; ++i) {
            string lft=s.substr(0, i), rvt=t, rit=s.substr(i);

            reverse(rvt.begin(), rvt.end());
            reverse(lft.begin(), lft.end());
            vector<int> lp=lps(lft+"$"+rvt), rp=lps(rit+"$"+t);

            for(int j=0; j<=M; ++j) {
                int len=rp[N-i+j]+lp[i+M-j];
                ans=max(ans, {len, {i-lp[i+M-j], (r?M-(j-rp[N-i+j]+len-1)-1:j-rp[N-i+j])}});
            }
        }

        reverse(begin(t), end(t));
    }

    cout<<ans.f<<el<<ans.s.f<<" "<<ans.s.s<<el;
}

// MM

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 6 ms 332 KB Output is correct
7 Correct 5 ms 332 KB Output is correct
8 Correct 5 ms 356 KB Output is correct
9 Correct 5 ms 332 KB Output is correct
10 Correct 5 ms 332 KB Output is correct
11 Correct 6 ms 332 KB Output is correct
12 Correct 5 ms 332 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 6 ms 332 KB Output is correct
7 Correct 5 ms 332 KB Output is correct
8 Correct 5 ms 356 KB Output is correct
9 Correct 5 ms 332 KB Output is correct
10 Correct 5 ms 332 KB Output is correct
11 Correct 6 ms 332 KB Output is correct
12 Correct 5 ms 332 KB Output is correct
13 Correct 274 ms 556 KB Output is correct
14 Correct 205 ms 580 KB Output is correct
15 Correct 290 ms 436 KB Output is correct
16 Correct 220 ms 432 KB Output is correct
17 Correct 283 ms 384 KB Output is correct
18 Correct 206 ms 432 KB Output is correct
19 Correct 217 ms 440 KB Output is correct
20 Correct 288 ms 492 KB Output is correct
21 Correct 237 ms 432 KB Output is correct