oj.uz

Submission #976298

# Submission time Handle Problem Language Result Execution time Memory
976298 2024-05-06T11:59:44 Z roctes7 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
25 / 85
 8 ms 4956 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
const double eps = 1e-6;
const int MAX = 3e3+3;

int pi[3003][3003];
int n;
string s;


void kmp(int sta){
    for (int i = 1; i < n; i++) {
        int j = pi[sta][i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[sta][j-1];
        if (s[i] == s[j])
            j++;
        pi[sta][i] = j;
    }
}

string t1,t2;
pair<int,pair<int,int>> solve(){
       for(int i=0;i<t1.size();i++){
        s = "";
        for(int j=i;j<t1.size();j++)s+=t1[j];
        for(int j=0;j<i;j++)s+=t1[j];
        s+="#";
        s+=t2;
        n = s.size();
        kmp(i);
        //cout<<s<<endl;
   }


   int l = 1;
   int r = t1.size();

   int ans = -1;
   int ansl = -1;
   int ansr = -1;

   while(l<=r){
        int k = (l+r)/2;
        bool check = false;
        for(int i=0;i<t1.size();i++){
            if(check)break;
            for(int j=t1.size()+1;j<n;j++){
                int cur = pi[i][j];
                if(cur>=k){
                    check = true;
                    if(cur>ans){
                        ans = cur;
                        ansl = i;
                        ansr = j-(t1.size()+1)-ans+1;
                    }
                    break;
                }
                int stil = k - cur;
                if(cur==0||i+cur>=t1.size()||j-cur<t1.size()+1)continue;

                int cur2 = pi[i+cur][j-cur];
                if(cur2>=stil){
                    check = true;
                    if(cur+cur2>ans){
                        ans = cur+cur2;
                        ansl = i;
                        ansr = j-(t1.size()+1)-ans+1;
                    }
                    break;
                }
            }
        }

        if(check){
            l = k+1;
        }else r = k-1;
   }
   return {ans,{ansl,ansr}};
}


int main(){
    fastio;



   cin>>t1>>t2;



     auto ans1 = solve();


    reverse(t2.begin(),t2.end());

    auto ans2 = solve();
    ans2.se.se = ans2.se.se + ans2.fi-1;
    ans2.se.se = t2.size()-ans2.se.se-1;
    if(ans2.se.se<0)ans2.se.se = t2.size()-1+ans2.se.se;

    pair<int,pair<int,int>> ans = max(ans1,ans2);

    cout<<ans.fi<<endl<<ans.se.fi<<" "<<ans.se.se;

    return 0;
}

Compilation message

necklace.cpp: In function 'std::pair<int, std::pair<int, int> > solve()':
necklace.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |        for(int i=0;i<t1.size();i++){
      |                    ~^~~~~~~~~~
necklace.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(int j=i;j<t1.size();j++)s+=t1[j];
      |                     ~^~~~~~~~~~
necklace.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int i=0;i<t1.size();i++){
      |                     ~^~~~~~~~~~
necklace.cpp:66:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |                 if(cur==0||i+cur>=t1.size()||j-cur<t1.size()+1)continue;
      |                            ~~~~~^~~~~~~~~~~
necklace.cpp:66:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |                 if(cur==0||i+cur>=t1.size()||j-cur<t1.size()+1)continue;
      |                                              ~~~~~^~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 2 ms 856 KB Output is correct
5 Correct 1 ms 860 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 2 ms 856 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 7 ms 4956 KB Output is correct
7 Correct 7 ms 4956 KB Output is correct
8 Incorrect 8 ms 4956 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 2 ms 856 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 7 ms 4956 KB Output is correct
7 Correct 7 ms 4956 KB Output is correct
8 Incorrect 8 ms 4956 KB Output isn't correct
9 Halted 0 ms 0 KB -