oj.uz

Submission #348377

# Submission time Handle Problem Language Result Execution time Memory
348377 2021-01-14T20:07:05 Z ahoraSoyPeor Necklace (Subtask 1-3) (BOI19_necklace1) C++14
85 / 85
 206 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
25.0 / 25.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 6 ms 400 KB Output is correct
7 Correct 4 ms 364 KB Output is correct
8 Correct 5 ms 364 KB Output is correct
9 Correct 4 ms 364 KB Output is correct
10 Correct 5 ms 364 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 4 ms 364 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 6 ms 400 KB Output is correct
7 Correct 4 ms 364 KB Output is correct
8 Correct 5 ms 364 KB Output is correct
9 Correct 4 ms 364 KB Output is correct
10 Correct 5 ms 364 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 4 ms 364 KB Output is correct
13 Correct 196 ms 492 KB Output is correct
14 Correct 170 ms 620 KB Output is correct
15 Correct 206 ms 620 KB Output is correct
16 Correct 170 ms 620 KB Output is correct
17 Correct 129 ms 492 KB Output is correct
18 Correct 141 ms 620 KB Output is correct
19 Correct 145 ms 492 KB Output is correct
20 Correct 165 ms 492 KB Output is correct
21 Correct 183 ms 620 KB Output is correct