oj.uz

Submission #928877

# Submission time Handle Problem Language Result Execution time Memory
928877 2024-02-17T07:28:14 Z UmairAhmadMirza Necklace (Subtask 1-3) (BOI19_necklace1) C++17
9 / 85
 140 ms 8072 KB 
#include <iostream>
using namespace std;
#define int long long
int const N=405;
int const mod=1e10+1;
int const base=1e5+237;
int hsh1[N][N];
int hsh2[N][N];
int r_hsh1[N][N];
int r_hsh2[N][N];
int min_hsh1[N][N];
int min_hsh2[N][N];
// map<int,bool> mp1;
// map<int,bool> mp2;
int pw[N];
string a,b;
void make_hash1(){
  int n=a.length();
  for(int i=1;i<=n;i++){
    int h1=0;
    for(int j=i;j<=n;j++){
      h1*=base;
      h1%=mod;
      h1+=a[j-1];
      h1%=mod;
      hsh1[i][j]=h1;
    }
  }
  for(int i=n;i>=1;i--){
    int h1=0;
    for(int j=i;j>=1;j--){
      h1*=base;
      h1%=mod;
      h1+=a[j-1];
      h1%=mod;
      r_hsh1[j][i]=h1;
    }
  }
}
void make_hash2(){
  int n=b.length();
  for(int i=1;i<=n;i++){
    int h1=0;
    for(int j=i;j<=n;j++){
      h1*=base;
      h1%=mod;
      h1+=b[j-1];
      h1%=mod;
      hsh2[i][j]=h1;
    }
  }
  for(int i=n;i>=1;i--){
    int h1=0;
    for(int j=i;j>=1;j--){
      h1*=base;
      h1%=mod;
      h1+=b[j-1];
      h1%=mod;
      r_hsh2[j][i]=h1;
    }
  }
}
void set_hsh1(){
  int n=a.length();
  int h=0;
  for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++){
      min_hsh1[i][j]=hsh1[i][j];
      for(int k=i;k<=j;k++){
        h=(hsh1[k][j]*pw[k-i])%mod;
        h+=hsh1[i][k-1];
        h%=mod;
        min_hsh1[i][j]=min(min_hsh1[i][j],h);
      }
      // cout<<i<<' '<<j<<' '<<min_hsh1[i][j]<<endl;
    }
  
  for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++){
      // min_hsh1[i][j]=hsh2[i][j];
      for(int k=i;k<=j;k++){
        h=(r_hsh1[i][k]*pw[j-k])%mod;
        h+=r_hsh1[k+1][j];
        h%=mod;
        min_hsh1[i][j]=min(min_hsh1[i][j],h);
      }
      // cout<<i<<' '<<j<<' '<<min_hsh1[i][j]<<endl;
    }
}
void set_hsh2(){
  int n=b.length();
  int h=0;
  for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++){
      min_hsh2[i][j]=hsh2[i][j];
      for(int k=i;k<=j;k++){
        h=(hsh2[k][j]*pw[k-i])%mod;
        h+=hsh2[i][k-1];
        h%=mod;
        min_hsh2[i][j]=min(min_hsh2[i][j],h);
      }
      // cout<<i<<' '<<j<<' '<<min_hsh2[i][j]<<endl;
    }
  
  for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++){
      for(int k=i;k<=j;k++){
        h=(r_hsh2[i][k]*pw[j-k])%mod;
        h+=r_hsh2[k+1][j];
        h%=mod;
        min_hsh2[i][j]=min(min_hsh2[i][j],h);
      }
      // cout<<i<<' '<<j<<' '<<min_hsh2[i][j]<<endl;
    }
}
void pwer(){
  pw[0]=1;
  for(int i=1;i<N;i++)
    pw[i]=(pw[i-1]*base)%mod;
}

signed main() 
{
  cin>>a>>b;
  pwer();
  make_hash1();
  make_hash2();
  set_hsh1();
  set_hsh2();
  int n=a.length();
  int m=b.length();
  for(int l=n-1;l>=0;l--)
    for(int i=1;i<=(n-l);i++)
      for(int j=1;j<=m-l;j++){
        if(min_hsh1[i][i+l]==min_hsh2[j][j+l]){
          cout<<l+1<<endl;
          cout<<i-1<<' '<<j-1<<endl;
          return 0;
        }
      }
}

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 7004 KB Output is partially correct
2 Partially correct 3 ms 7004 KB Output is partially correct
3 Partially correct 3 ms 7004 KB Output is partially correct
4 Partially correct 3 ms 7092 KB Output is partially correct
5 Partially correct 4 ms 7004 KB Output is partially correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 7004 KB Output is partially correct
2 Partially correct 3 ms 7004 KB Output is partially correct
3 Partially correct 3 ms 7004 KB Output is partially correct
4 Partially correct 3 ms 7092 KB Output is partially correct
5 Partially correct 4 ms 7004 KB Output is partially correct
6 Partially correct 136 ms 8016 KB Output is partially correct
7 Partially correct 129 ms 8016 KB Output is partially correct
8 Partially correct 105 ms 7840 KB Output is partially correct
9 Partially correct 122 ms 8036 KB Output is partially correct
10 Partially correct 134 ms 8072 KB Output is partially correct
11 Partially correct 140 ms 7892 KB Output is partially correct
12 Partially correct 140 ms 7828 KB Output is partially correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 7004 KB Output is partially correct
2 Partially correct 3 ms 7004 KB Output is partially correct
3 Partially correct 3 ms 7004 KB Output is partially correct
4 Partially correct 3 ms 7092 KB Output is partially correct
5 Partially correct 4 ms 7004 KB Output is partially correct
6 Partially correct 136 ms 8016 KB Output is partially correct
7 Partially correct 129 ms 8016 KB Output is partially correct
8 Partially correct 105 ms 7840 KB Output is partially correct
9 Partially correct 122 ms 8036 KB Output is partially correct
10 Partially correct 134 ms 8072 KB Output is partially correct
11 Partially correct 140 ms 7892 KB Output is partially correct
12 Partially correct 140 ms 7828 KB Output is partially correct
13 Runtime error 11 ms 3160 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -