Submission #1073400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073400		mimi	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	204 ms	216700 KiB

selling_rna

#include <bits/stdc++.h>
//#ifndef ONLINE_JUDGE
//#include <debugging.h>
//#endif
#define pp push_back
#define all(x) (x).begin(),(x).end()
#define dbg(v)  cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
using namespace std;
const char el ='\n';
const char sp = ' ';
const int maxn = 2e6+5;
int n,m;
string s[maxn];

int binsearch(const string& a)
{
    int l = 1, r = n, mid;
    while(l<=r)
    {
        mid = (l+r)/2;
        int flag = 0;
        for(int i=0;i<a.size();++i){
            if(i>=s[mid].size() or s[mid][i]!=a[i]){
                if(a[i]>s[mid][i])  flag = 1;
                else                flag = 2;
                break;
            }
        }
        if(flag==1)    l = mid + 1;
        else           r = mid - 1;
    }
    return l;
}

int binsearch1(const string& a)
{
    int l = 1, r = n, mid;
    while(l<=r)
    {
        mid = (l+r)/2;
        int flag = 0;
        for(int i=0;i<a.size();++i){
            if(i>=s[mid].size() or s[mid][i]!=a[i]){
                if(a[i]>s[mid][i])  flag = 1;
                else                flag = 2;
                break;
            }
        }
        if(flag==1 or flag ==0)    l = mid + 1;
        else                       r = mid - 1;
    }
    return r;
}

struct Trie
{
    int trie[maxn][5],curnode = 0;
    vector <int> id[maxn];

    void add(const string& a, int id_)
    {
        int node = 0;
        for(char c:a)
        {
            if(!trie[node][c-'a'])  trie[node][c-'a'] = ++curnode;
            node = trie[node][c-'a'];
            id[node].pp(id_);
        }
    }

    int cal(const string& a, int l, int r)
    {
        int node = 0;
        for(char c:a)
        {
            if(!trie[node][c-'a'])  return 0;
            node = trie[node][c-'a'];
        }
        int le = lower_bound(all(id[node]),l) - id[node].begin();
        int ri = upper_bound(all(id[node]),r) - id[node].begin();
        return ri - le;
    }
}f;

char cal(char c)
{
    if(c=='A')  return 'a';
    if(c=='U')  return 'b';
    if(c=='G')  return 'c';
    if(c=='C')  return 'd';
}

void input()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        cin>>s[i];
        for(int j=0;j<s[i].size();++j)  s[i][j] = cal(s[i][j]);
    }
    sort(s+1,s+n+1);
//    for(int i=1;i<=n;++i)   cout<<i<<sp<<s[i]<<endl;
    for(int i=1;i<=n;++i)
    {
        string tmp = s[i];
        reverse(all(tmp));
        f.add(tmp,i);
    }
    for(int i=0;i<=f.curnode;++i) sort(all(f.id[i]));
}

void solve()
{
    string p,q;
    for(int i=1;i<=m;++i)
    {
        cin>>p>>q;
        for(int j=0;j<p.size();++j) p[j] = cal(p[j]);
        for(int j=0;j<q.size();++j) q[j] = cal(q[j]);
        reverse(all(q));
        int l = binsearch(p), r = binsearch1(p);
//        cout<<l<<sp<<r<<endl;
        cout<<f.cal(q,l,r)<<el;
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    solve();
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int binsearch(const string&)':
selling_rna.cpp:22:22: 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=0;i<a.size();++i){
      |                     ~^~~~~~~~~
selling_rna.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |             if(i>=s[mid].size() or s[mid][i]!=a[i]){
      |                ~^~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int binsearch1(const string&)':
selling_rna.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int i=0;i<a.size();++i){
      |                     ~^~~~~~~~~
selling_rna.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             if(i>=s[mid].size() or s[mid][i]!=a[i]){
      |                ~^~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void input()':
selling_rna.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int j=0;j<s[i].size();++j)  s[i][j] = cal(s[i][j]);
      |                     ~^~~~~~~~~~~~
selling_rna.cpp: In function 'void solve()':
selling_rna.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(int j=0;j<p.size();++j) p[j] = cal(p[j]);
      |                     ~^~~~~~~~~
selling_rna.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(int j=0;j<q.size();++j) q[j] = cal(q[j]);
      |                     ~^~~~~~~~~
selling_rna.cpp: In function 'char cal(char)':
selling_rna.cpp:91:1: warning: control reaches end of non-void function [-Wreturn-type]
   91 | }
      | ^

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40