oj.uz

Submission #928803

# Submission time Handle Problem Language Result Execution time Memory
928803 2024-02-17T06:01:45 Z Muhammad_Aneeq Necklace (Subtask 1-3) (BOI19_necklace1) C++17
9 / 85
 1500 ms 648 KB 
/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
int mod=1e9+7;
int power(int x,int y)
{
  int res=1;
  while (y)
  {
    if (y&1)
      res=(res*x)%mod;
    x=(x*x)%mod;
    y>>=1;
  }
  return res;
}
string x,y;
bool check(int i,int j,int k)
{
  string a,b;
  for (int l=i;l<i+k;l++)
    a+=x[l];
  for (int l=j;l<j+k;l++)
    b+=y[l];
  reverse(begin(a),end(a));
  for (int i=0;i<b.size();i++)
  {
    char g=b.back();
    b.pop_back();
    b=g+b;
    if (b==a)
      return 1;
  }
  return 0;
}
vector<int>pr={2,3,5,7,11,13,17,19,23,29,31,37,41,43,53,59,61,67,71,73,79,83,89,97,101};
inline void solve()
{
  cin>>x>>y;
  int n=x.size(),m=y.size();
  int hash[n+1]={};
  int hash1[m+1]={};
  hash[0]=hash1[0]=1;
  for (int i=0;i<n;i++)
    hash[i+1]=(hash[i]*pr[x[i]-'a'])%mod;
  for (int i=0;i<m;i++)
    hash1[i+1]=(hash1[i]*pr[y[i]-'a'])%mod;
  int ans=0,l,r;
  for (int k=1;k<=min(n,m);k++)
  {
    map<int,vector<int>>d;
    for (int i=0;i<=n-k;i++)
    {
      int z=(hash[i+k]*power(hash[i],mod-2))%mod;
      d[z].push_back(i);
    }
    for (int j=0;j<=m-k;j++)
    {
        int z=(hash1[j+k]*power(hash1[j],mod-2))%mod;
        if (d.find(z)!=d.end())
        {
          if (ans<k)
          {
            if (check(d[z][0],j,k))
            {
              ans=k;
              l=d[z][0],r=j;
            }
          }
        }
    }
  }
  cout<<ans<<endl;
  cout<<l<<' '<<r<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);   
        solve();
}

Compilation message

necklace.cpp: In function 'bool check(long long int, long long int, long long int)':
necklace.cpp:35:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int i=0;i<b.size();i++)
      |                ~^~~~~~~~~

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Partially correct 8 ms 348 KB Output is partially correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Partially correct 8 ms 348 KB Output is partially correct
6 Correct 68 ms 468 KB Output is correct
7 Partially correct 69 ms 480 KB Output is partially correct
8 Correct 67 ms 448 KB Output is correct
9 Partially correct 82 ms 348 KB Output is partially correct
10 Correct 102 ms 500 KB Output is correct
11 Partially correct 145 ms 488 KB Output is partially correct
12 Partially correct 213 ms 456 KB Output is partially correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Partially correct 8 ms 348 KB Output is partially correct
6 Correct 68 ms 468 KB Output is correct
7 Partially correct 69 ms 480 KB Output is partially correct
8 Correct 67 ms 448 KB Output is correct
9 Partially correct 82 ms 348 KB Output is partially correct
10 Correct 102 ms 500 KB Output is correct
11 Partially correct 145 ms 488 KB Output is partially correct
12 Partially correct 213 ms 456 KB Output is partially correct
13 Execution timed out 1584 ms 648 KB Time limit exceeded
14 Halted 0 ms 0 KB -