oj.uz

Submission #1106451

# Submission time Handle Problem Language Result Execution time Memory
1106451 2024-10-30T10:58:41 Z fatman87878 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 512 KB 
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long
#define u64 unsigned long long
 
constexpr int maxN=2e5+5;
 
constexpr u64 C = 998244353;
 
string s,t;
 
int a,b;
 
inline bool chk(int guess){
    map<u64,int> hashs;
    u64 hsh=0,x=1;
    for(int i = 0;i<guess-1;i++)x*=C;
    for(int i = 0;i<guess-1;i++)hsh*=C,hsh+=t[i];
    for(int i = guess-1;i<t.size();i++){
        hsh*=C,hsh+=t[i];
        hashs[hsh]=i-guess+1;
        hsh-=x*t[i-guess+1];
    }
    for(int i = 0;i+guess<=s.size();i++){
        u64 fh=0,bh=0;
        for(int j = 0;j<guess;j++)bh*=C,bh+=s[j+i];
        for(int j = 0;j<guess;j++){
            fh*=C;
            fh+=s[j+i];
            bh-=x*s[j+i];
            bh*=C;
            if(hashs.count(fh+bh)){
                a=i,b=hashs[fh+bh];
                return 1;
            }
        }
        u64 fh2=0,bh2=0;
        for(int j = guess;j--;)fh2*=C,fh2+=s[j+i];
        for(int j = guess;j--;){
            bh2*=C;
            bh2+=s[j+i];
            fh2-=x*s[j+i];
            fh2*=C;
            if(hashs.count(fh2+bh2)){
                a=i,b=hashs[fh2+bh2];
                return 1;
            }
        }
    }
    return 0;
}
 
int main(){
    IOS
    cin>>s>>t;
    int l = 0,r = min(s.size(),t.size()),mid;
    for(int i = r;i>=l;i--){
        if(chk(i)){
            return cout<<i<<'\n'<<a<<' '<<b<<'\n',0;
        }
    }
}

Compilation message

necklace.cpp: In function 'bool chk(int)':
necklace.cpp:22:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i = guess-1;i<t.size();i++){
      |                         ~^~~~~~~~~
necklace.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i = 0;i+guess<=s.size();i++){
      |                   ~~~~~~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:59:42: warning: unused variable 'mid' [-Wunused-variable]
   59 |     int l = 0,r = min(s.size(),t.size()),mid;
      |                                          ^~~

Subtask #1
25.0 / 25.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 8 ms 336 KB Output is correct
6 Correct 20 ms 336 KB Output is correct
7 Correct 38 ms 512 KB Output is correct
8 Correct 200 ms 452 KB Output is correct
9 Correct 368 ms 336 KB Output is correct
10 Correct 604 ms 448 KB Output is correct
11 Correct 647 ms 336 KB Output is correct
12 Correct 393 ms 336 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 8 ms 336 KB Output is correct
6 Correct 20 ms 336 KB Output is correct
7 Correct 38 ms 512 KB Output is correct
8 Correct 200 ms 452 KB Output is correct
9 Correct 368 ms 336 KB Output is correct
10 Correct 604 ms 448 KB Output is correct
11 Correct 647 ms 336 KB Output is correct
12 Correct 393 ms 336 KB Output is correct
13 Execution timed out 1558 ms 336 KB Time limit exceeded
14 Halted 0 ms 0 KB -