oj.uz

Submission #348376

# Submission time Handle Problem Language Result Execution time Memory
348376 2021-01-14T20:05:51 Z ahoraSoyPeor Necklace (Subtask 4) (BOI19_necklace4) C++14
15 / 15
 220 ms 620 KB 
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;

const int N = 6'005;
const int MOD = 1'000'000'007;
const int LOGN = 17;

//int mul ( int A, int B ) { return int((ll(A)*ll(B))%ll(MOD)); }
//int add ( int A, int B ) { return A+B >= MOD? A+B-MOD: A+B; }
//int sub ( int A, int B ) { return add ( A, MOD-B ); }

string A, rA, B, rB, S1, S2;
int szA, szB;

int kmp1[N], kmp2[N];

void calcKMP ( string &str, int sz, int* arr ) {
  arr[0] = arr[sz] = 0;
  int it = 0;
  for ( int i = 1; i < sz; ++i ) {
    while ( it > 0 and str[it] != str[i] )
      it = arr[it-1];
    if ( str[it] == str[i] ) ++it;
    arr[i] = it;
  }
}

int res, indA, indB;
bool rFlag;

void calc ( bool flag ) {
  for ( int i = 0; i <= szA; ++i ) {
    S1 = rA.substr (szA-i,i) + '#' + rB;
    S2 = A.substr (i,szA-i) + '#' + B;
    calcKMP ( S1, S1.size(), kmp1 );
    calcKMP ( S2, S2.size(), kmp2 );
    for ( int h = 0; h <= szB; ++h ) {
      int itA = i+szB-h, itB = szA-i+h;
      if ( res < kmp1[itA]+kmp2[itB] ) {
        res = kmp1[itA]+kmp2[itB], rFlag = flag;
        indA = i-kmp1[itA]; indB = h-kmp2[itB];
      }
    }
  }
}

int main () {

  ios_base::sync_with_stdio(0);
  cin.tie(0);

  #ifdef LOCAL
    freopen ( "in.txt", "r", stdin );
  #endif // LOCAL

  cin >> A >> B;
  szA = A.size(), szB = B.size();
  rA = A; rB = B;
  reverse ( rA.begin(), rA.end() );
  reverse ( rB.begin(), rB.end() );
  calc ( false );
  swap ( A, rA );
  calc ( true );
  if ( rFlag )
    indA = szA-indA-res;
  printf ( "%d\n%d %d\n", res, indA, indB );

  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 492 KB Output is correct
2 Correct 158 ms 492 KB Output is correct
3 Correct 220 ms 620 KB Output is correct
4 Correct 146 ms 492 KB Output is correct
5 Correct 122 ms 620 KB Output is correct
6 Correct 138 ms 620 KB Output is correct
7 Correct 147 ms 492 KB Output is correct
8 Correct 169 ms 492 KB Output is correct
9 Correct 175 ms 492 KB Output is correct