oj.uz

Submission #976797

# Submission time Handle Problem Language Result Execution time Memory
976797 2024-05-07T06:38:32 Z yeediot Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 50140 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
struct line{
    int a,b;
    int operator()(const int x)const{
        return a*x+b;
    }
};
bool check(line l1,line l2,line l3){
    return (l3.b-l2.b)*(l1.a-l2.a)<=(l2.b-l1.b)*(l2.a-l3.a);
}
const int mxn=1e5+5;
const int mxl=2e6+5;
const int mod=1e9+7;
const int p=3773;
int n, m, pw[mxl];
vector<int>hsh[mxn];
string s[mxn];
int get(int id,int l,int r){
    if(l==0)return hsh[id][r]; 
    return ((hsh[id][r]-hsh[id][l-1]*pw[r-l+1]%mod)%mod+mod)%mod;
}
signed main(){
    setio();
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    pw[0]=1;
    for(int i=1;i<mxl;i++){
        pw[i]=pw[i-1]*p%mod;
    }
    for(int i=1;i<=n;i++){
        cin>>s[i];
        int prv=0;
        for(int j=0;j<sz(s[i]);j++){
            prv=(prv*p%mod+s[i][j]-'A'+1)%mod;
            hsh[i].pb(prv);
        }
    }
    for(int i=1;i<=m;i++){
        string a,b;
        cin>>a>>b;
        int hsha=0,hshb=0;
        for(int j=0;j<sz(a);j++){
            hsha=(hsha*p%mod+a[j]-'A'+1)%mod;
        }
        for(int j=0;j<sz(b);j++){
            hshb=(hshb*p%mod+b[j]-'A'+1)%mod;
        }
        int cnt=0;
        for(int j=1;j<=n;j++){
            if(sz(a)>sz(s[j]) or sz(s[j])-sz(b)<0)continue;
            if(get(j,0,sz(a)-1)==hsha and get(j,sz(s[j])-sz(b),sz(s[j])-1)==hshb){
                cnt++;
            }
        }
        cout<<cnt<<'\n';
    }
}
 /*
 input:
 
 */

Compilation message

selling_rna.cpp: In function 'void setIO(std::string)':
selling_rna.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21340 KB Output is correct
2 Correct 20 ms 21352 KB Output is correct
3 Correct 12 ms 21592 KB Output is correct
4 Correct 12 ms 21340 KB Output is correct
5 Correct 12 ms 21396 KB Output is correct
6 Correct 12 ms 21340 KB Output is correct
7 Correct 12 ms 21340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 43344 KB Output is correct
2 Correct 361 ms 49512 KB Output is correct
3 Correct 152 ms 48220 KB Output is correct
4 Correct 199 ms 49232 KB Output is correct
5 Correct 180 ms 38572 KB Output is correct
6 Correct 161 ms 38668 KB Output is correct
7 Correct 181 ms 44368 KB Output is correct
8 Correct 200 ms 50140 KB Output is correct
9 Correct 224 ms 50108 KB Output is correct
10 Correct 692 ms 47844 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21340 KB Output is correct
2 Correct 20 ms 21352 KB Output is correct
3 Correct 12 ms 21592 KB Output is correct
4 Correct 12 ms 21340 KB Output is correct
5 Correct 12 ms 21396 KB Output is correct
6 Correct 12 ms 21340 KB Output is correct
7 Correct 12 ms 21340 KB Output is correct
8 Correct 107 ms 43344 KB Output is correct
9 Correct 361 ms 49512 KB Output is correct
10 Correct 152 ms 48220 KB Output is correct
11 Correct 199 ms 49232 KB Output is correct
12 Correct 180 ms 38572 KB Output is correct
13 Correct 161 ms 38668 KB Output is correct
14 Correct 181 ms 44368 KB Output is correct
15 Correct 200 ms 50140 KB Output is correct
16 Correct 224 ms 50108 KB Output is correct
17 Correct 692 ms 47844 KB Output is correct
18 Execution timed out 1550 ms 23172 KB Time limit exceeded
19 Halted 0 ms 0 KB -