oj.uz

Submission #146456

# Submission time Handle Problem Language Result Execution time Memory
146456 2019-08-24T07:50:08 Z Alexa2001 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 256 ms 508 KB 
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 3005;


string A, B, Brev;
int startA, startB, best = 0;

int z1[Nmax], z2[Nmax];
int pi[Nmax];


void kmp(string &A, string &B, int mat[])
{
    int i, k;

    pi[1] = 0;
    for(i=2; i<=A.size(); ++i)
    {
        k = pi[i-1];
        while(k && A[k] != A[i-1]) k = pi[k];
        
        if(A[k] == A[i-1]) ++k;
        pi[i] = k;
    }

    k = 0;
    for(i=1; i<=B.size(); ++i)
    {
        while(k && A[k] != B[i-1]) k = pi[k];

        if(A[k] == B[i-1]) ++k;
        mat[i-1] = k;
    }
}

void solve(bool rev)
{
    if(rev) swap(B, Brev);

    int i, j;

    for(i=0; i<=A.size(); ++i)
    {
        string A1, A2;

        A1 = A.substr(0, i); /// 0...i-1
        A2 = A.substr(i, A.size() - i); /// i...A.size()-1

     //   cerr << i << ' ' << A1 << ' ' << A2 << ' ' << '\n';

        reverse(A1.begin(), A1.end());
            
        kmp(A1, Brev, z1);
        kmp(A2, B, z2);

        for(j=0; j<=B.size(); ++j)
        {
            int curr;
            int curr1 = 0, curr2 = 0;
            if(j > 0) curr1 = z2[j-1];
            if(j < B.size()) curr2 = z1[B.size() - j - 1];
            
            curr = curr1 + curr2;

            if(curr > best) 
            {
   /*            if(curr == 4)
                {
                    cerr << (rev ? 1 : 0) << '\n';
                    cerr << A1 << ' ' << A2 << '\n';
                    cerr << curr1 << ' ' << curr2 << '\n';
                }
*/
                best = curr;
                startA = i - curr2;
                startB = j - curr1;

                if(rev) startB = B.size() - 1 - startB - curr + 1;
            }
        }
    }
}

int main()
{
  //  freopen("necklace.in", "r", stdin);
    cin.tie(0); cin.sync_with_stdio(false);

    cin >> A >> B;

    Brev = B;
    reverse(Brev.begin(), Brev.end());
    
    solve(0);
    solve(1);

    cout << best << '\n' << startA << ' ' << startB << '\n';

    return 0;
}

Compilation message

necklace.cpp: In function 'void kmp(std::__cxx11::string&, std::__cxx11::string&, int*)':
necklace.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=2; i<=A.size(); ++i)
              ~^~~~~~~~~~
necklace.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=1; i<=B.size(); ++i)
              ~^~~~~~~~~~
necklace.cpp: In function 'void solve(bool)':
necklace.cpp:45:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<=A.size(); ++i)
              ~^~~~~~~~~~
necklace.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<=B.size(); ++j)
                  ~^~~~~~~~~~
necklace.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(j < B.size()) curr2 = z1[B.size() - j - 1];
                ~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 7 ms 508 KB Output is correct
8 Correct 7 ms 424 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 6 ms 420 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 6 ms 504 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 7 ms 508 KB Output is correct
8 Correct 7 ms 424 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 6 ms 420 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 6 ms 504 KB Output is correct
13 Correct 226 ms 440 KB Output is correct
14 Correct 185 ms 420 KB Output is correct
15 Correct 256 ms 440 KB Output is correct
16 Correct 210 ms 376 KB Output is correct
17 Correct 150 ms 376 KB Output is correct
18 Correct 159 ms 444 KB Output is correct
19 Correct 170 ms 472 KB Output is correct
20 Correct 196 ms 376 KB Output is correct
21 Correct 206 ms 440 KB Output is correct