oj.uz

Submission #209620

# Submission time Handle Problem Language Result Execution time Memory
209620 2020-03-14T22:15:36 Z thebes Necklace (Subtask 1-3) (BOI19_necklace1) C++14
9 / 85
 1349 ms 504 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,ssse3,sse3,sse4,popcnt,avx,mmx,abm,tune=native")
#include <bits/stdc++.h>
#define DEBUG 1
using namespace std;

namespace output{
    void __(short x){cout<<x;}
    void __(unsigned x){cout<<x;}
    void __(int x){cout<<x;}
    void __(long long x){cout<<x;}
    void __(unsigned long long x){cout<<x;}
    void __(double x){cout<<x;}
    void __(long double x){cout<<x;}
    void __(char x){cout<<x;}
    void __(const char*x){cout<<x;}
    void __(const string&x){cout<<x;}
    void __(bool x){cout<<(x?"true":"false");}
    template<class S,class T>
    void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");}
    template<class T>
    void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class T>
    void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class T>
    void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class S,class T>
    void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    void pr(){cout<<"\n";}
    template<class S,class... T>
    void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);}
}

using namespace output;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,char> pic;
typedef pair<double,double> pdd;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,vi> piv;

#define pb push_back
#define fox(i,x,y) for(int i=(x);i<=(y);i++)
#define foxr(i,x,y) for(int i=(y);i>=(x);i--)

const int MN = 3003;
string s, t;
int n, m, i, hsh[2][MN], pw[MN]={1}, pre[MN], suf[MN], st[MN], len[MN], lo, hi, lim1, lim2, ans, sw, fl, ree, k, sh, mid;
inline int gethsh(int id,int x,int y){return hsh[id][y]-hsh[id][x-1]*pw[y-x+1];}
pii sna; queue<pii> hm;

void solve(int init=0){
    for(int i=1;i<=m;i++)
        hsh[1][i]=hsh[1][i-1]*133+t[i-1]-'a'+1;
    k = min(m,lim2);
    for(int i=1;i<=n;i++){
        if(init||i==n){
            lo=0, hi=min(i,k);
            while(lo<hi){
                mid = (lo+hi)/2;
                if(gethsh(0,i-mid,i)==gethsh(1,m-mid,m)) lo=mid+1;
                else hi=mid;
            }
            suf[i]=lo;
        }
        else{
            suf[i]=max(0,suf[i+1]-1);
        }
    }
    while(hm.size()) hm.pop();
    for(int i=n;i>=1;i--){
        if(suf[i]) hm.push({suf[i],i});
        while(hm.size()){
            if(hm.front().second-hm.front().first+1>i) hm.pop();
            else break;
        }
        if(hm.size()){
            st[i] = lim2-hm.front().first;
            len[i] = hm.front().second-i+1;
        }
        else len[i] = 0, st[i] = lim2;  
    }
    k = min(m,lim1);
    for(int i=1;i<=n;i++){
        if(s[i-1]!=t[0]){
            pre[i]=0;
            continue;
        }
        lo=0, hi=min(n-i+1,k);
        while(lo<hi){
            mid = (lo+hi)/2;
            if(gethsh(0,i,i+mid)==gethsh(1,1,1+mid)) lo=mid+1;
            else hi=mid;
        }
        pre[i]=lo;
    }
    while(hm.size()) hm.pop();
    for(int i=1;i<=n;i++){
        if(pre[i]) hm.push({pre[i],i});
        while(hm.size()){
            if(hm.front().second+hm.front().first-1<i) hm.pop();
            else break;
        }
        if(hm.size()){
            len[i] = i-hm.front().second+1;
            if(len[i]+len[i+1]>ans){
                ans = len[i]+len[i+1];
                if(sw) sna = {n-(i+len[i+1]), st[i+1]};
                else sna = {hm.front().second-1, st[i+1]};
            }
        }
    }
}

int main(){
    cin >> s >> t;
    n = s.size(), m = t.size();
    for(i=1;i<MN;i++)
        pw[i]=133*pw[i-1];
    for(i=1;i<=n;i++)
        hsh[0][i]=hsh[0][i-1]*133+s[i-1]-'a'+1;
    lim1 = 0; lim2 = m;
    solve(1);
    for(i=1;i<=m;i++){
        lim1++; lim2--;
        char ch = t.back(); t.erase(t.end()-1);
        t.insert(t.begin(),ch);
        solve();
    }
    for(i=0;i<s.size()/2;i++)
        swap(s[i],s[s.size()-i-1]);
    for(i=1;i<=n;i++)
        hsh[0][i]=hsh[0][i-1]*133+s[i-1]-'a'+1;
    lim1 = 0; lim2 = m; sw = 1;
    solve(1);
    for(i=1;i<=m;i++){
        lim1++; lim2--;
        char ch = t.back(); t.erase(t.end()-1);
        t.insert(t.begin(),ch);
        solve();
    }
    printf("%d\n%d %d\n",ans,sna.first,sna.second);
    return 0;
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:136:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<s.size()/2;i++)
             ~^~~~~~~~~~~

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 376 KB Output is partially correct
2 Partially correct 5 ms 376 KB Output is partially correct
3 Partially correct 6 ms 376 KB Output is partially correct
4 Partially correct 5 ms 376 KB Output is partially correct
5 Partially correct 5 ms 376 KB Output is partially correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 376 KB Output is partially correct
2 Partially correct 5 ms 376 KB Output is partially correct
3 Partially correct 6 ms 376 KB Output is partially correct
4 Partially correct 5 ms 376 KB Output is partially correct
5 Partially correct 5 ms 376 KB Output is partially correct
6 Partially correct 21 ms 376 KB Output is partially correct
7 Partially correct 13 ms 504 KB Output is partially correct
8 Partially correct 18 ms 376 KB Output is partially correct
9 Partially correct 16 ms 376 KB Output is partially correct
10 Partially correct 10 ms 376 KB Output is partially correct
11 Partially correct 8 ms 376 KB Output is partially correct
12 Correct 15 ms 376 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 376 KB Output is partially correct
2 Partially correct 5 ms 376 KB Output is partially correct
3 Partially correct 6 ms 376 KB Output is partially correct
4 Partially correct 5 ms 376 KB Output is partially correct
5 Partially correct 5 ms 376 KB Output is partially correct
6 Partially correct 21 ms 376 KB Output is partially correct
7 Partially correct 13 ms 504 KB Output is partially correct
8 Partially correct 18 ms 376 KB Output is partially correct
9 Partially correct 16 ms 376 KB Output is partially correct
10 Partially correct 10 ms 376 KB Output is partially correct
11 Partially correct 8 ms 376 KB Output is partially correct
12 Correct 15 ms 376 KB Output is correct
13 Partially correct 998 ms 468 KB Output is partially correct
14 Partially correct 620 ms 376 KB Output is partially correct
15 Partially correct 1349 ms 504 KB Output is partially correct
16 Partially correct 772 ms 376 KB Output is partially correct
17 Partially correct 211 ms 452 KB Output is partially correct
18 Partially correct 233 ms 380 KB Output is partially correct
19 Incorrect 638 ms 376 KB Output isn't correct
20 Halted 0 ms 0 KB -