oj.uz

Submission #976346

# Submission time Handle Problem Language Result Execution time Memory
976346 2024-05-06T12:56:21 Z roctes7 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
37 / 85
 536 ms 82772 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][7003];
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+="$";
        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(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;

    assert(ans2.se.se>=0);
    //if(ans2.se.se<0)ans2.se.se = t2.size()+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:25: 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(i+cur>=t1.size()||j-cur<t1.size()+1)continue;
      |                    ~~~~~^~~~~~~~~~~
necklace.cpp:66:43: 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(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 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 6 ms 4700 KB Output is correct
7 Correct 6 ms 4952 KB Output is correct
8 Partially correct 8 ms 3164 KB Output is partially correct
9 Correct 7 ms 4700 KB Output is correct
10 Correct 7 ms 4824 KB Output is correct
11 Correct 7 ms 4700 KB Output is correct
12 Correct 8 ms 4444 KB Output is correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 6 ms 4700 KB Output is correct
7 Correct 6 ms 4952 KB Output is correct
8 Partially correct 8 ms 3164 KB Output is partially correct
9 Correct 7 ms 4700 KB Output is correct
10 Correct 7 ms 4824 KB Output is correct
11 Correct 7 ms 4700 KB Output is correct
12 Correct 8 ms 4444 KB Output is correct
13 Correct 440 ms 82624 KB Output is correct
14 Correct 353 ms 82716 KB Output is correct
15 Partially correct 494 ms 80340 KB Output is partially correct
16 Partially correct 536 ms 82764 KB Output is partially correct
17 Correct 513 ms 82564 KB Output is correct
18 Correct 495 ms 82716 KB Output is correct
19 Correct 425 ms 82752 KB Output is correct
20 Correct 407 ms 82772 KB Output is correct
21 Correct 374 ms 82628 KB Output is correct