oj.uz

Submission #933074

# Submission time Handle Problem Language Result Execution time Memory
933074 2024-02-25T01:06:07 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 19792 KB 
#include <bits/stdc++.h>
#define endl '\n'
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define fore(i,l,r) for(int i = l; i < r;i++)
#define forex(i,r,l) for(int i = r; i>= l;i--)
#define fo(i,n) fore(i,0,n)
#define ffo(i,n) forex(i,n-1,0)
#define lsb(x) x&(-x)
using namespace std;
using ii = pair<int,int>;using ll = long long; using ull = unsigned long long;
using vi = vector<int>;
const int N = 1e5+7,mod=1e9+7,P=31;
ll po[N],ipo[N];
ll fpow(ll a, ll b, ll res = 1 ){
    while(b>0){
        if(b&1)res = (res * a) %mod;
        a = (a*a)%mod; b >>=1;
    }return res;
}
int to(char a){return a-'A'+1;}
struct hashing{
    vector<ll> hash1; int n;
    hashing(string &cad){n=cad.size();
        hash1.resize(n+4,0);
        // cout << n << endl;return;
        fore(i,1,n+1){
            hash1[i] = ((1ll*to(cad[i-1])*po[i])%mod + hash1[i-1])%mod;
            // cout << hash1[i] << " ";
        }
        // cout << endl;
    }
    pair<ll,ll> pre_suf(int l, int r ){
        ll num = (1ll*(hash1[n] - hash1[r-1]+mod)%mod*(ipo[r-1]))%mod;
        return mp(hash1[l],num);
    }
};
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m; cin >> n >> m;
    po[0]=1;ipo[0]=1;
    fore(i,1,N){po[i]=(po[i-1]*P)%mod;ipo[i]=fpow(po[i],mod-2);}
    vector<hashing> arr;
    fo(i,n){
        string cad; cin >> cad;
        hashing a(cad);
        arr.pb(a);
    }
    while(m--){
        string cad1,cad2;
        cin >> cad1 >> cad2;
        // cout << cad1.size() << " " << cad2<< endl;
        hashing a(cad1),b(cad2);
        int ans = 0;
        fo(i,n){
            if(cad1.size() > arr[i].n || cad2.size() > arr[i].n) continue;
            auto act = arr[i].pre_suf(cad1.size(),arr[i].n-cad2.size()+1);
            if(act.f == a.hash1[cad1.size()] and act.s == b.hash1[cad2.size()])ans++;
        }
        cout << ans << endl;
    }
}
/*
add(--l)
add(++r)
remove(l++)
remove(r--)
*/

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:59:28: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |             if(cad1.size() > arr[i].n || cad2.size() > arr[i].n) continue;
      |                ~~~~~~~~~~~~^~~~~~~~~~
selling_rna.cpp:59:54: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |             if(cad1.size() > arr[i].n || cad2.size() > arr[i].n) continue;
      |                                          ~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1884 KB Output is correct
2 Correct 13 ms 1884 KB Output is correct
3 Correct 13 ms 2016 KB Output is correct
4 Correct 13 ms 1992 KB Output is correct
5 Correct 13 ms 1880 KB Output is correct
6 Correct 13 ms 1884 KB Output is correct
7 Correct 13 ms 1884 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 17876 KB Output is correct
2 Correct 281 ms 18124 KB Output is correct
3 Correct 131 ms 17976 KB Output is correct
4 Correct 186 ms 18100 KB Output is correct
5 Correct 153 ms 12464 KB Output is correct
6 Correct 148 ms 12248 KB Output is correct
7 Correct 160 ms 19792 KB Output is correct
8 Correct 208 ms 17892 KB Output is correct
9 Correct 194 ms 18004 KB Output is correct
10 Correct 264 ms 18104 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1555 ms 6748 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1884 KB Output is correct
2 Correct 13 ms 1884 KB Output is correct
3 Correct 13 ms 2016 KB Output is correct
4 Correct 13 ms 1992 KB Output is correct
5 Correct 13 ms 1880 KB Output is correct
6 Correct 13 ms 1884 KB Output is correct
7 Correct 13 ms 1884 KB Output is correct
8 Correct 82 ms 17876 KB Output is correct
9 Correct 281 ms 18124 KB Output is correct
10 Correct 131 ms 17976 KB Output is correct
11 Correct 186 ms 18100 KB Output is correct
12 Correct 153 ms 12464 KB Output is correct
13 Correct 148 ms 12248 KB Output is correct
14 Correct 160 ms 19792 KB Output is correct
15 Correct 208 ms 17892 KB Output is correct
16 Correct 194 ms 18004 KB Output is correct
17 Correct 264 ms 18104 KB Output is correct
18 Execution timed out 1555 ms 6748 KB Time limit exceeded
19 Halted 0 ms 0 KB -