Submission #558853

#	Time	Username	Problem	Language	Result	Execution time	Memory
558853		groshi	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	274 ms	149336 KiB

selling_rna

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int jaki[30];
struct wi{
    vector<int> Q;
    int dokad[4];
}*w;
int nowy=2;
string t[100010];
void dodaj(int co,int gdzie_wco,int gdzie)
{
    w[gdzie].Q.push_back(co);
    if(gdzie_wco<0)
        return;
    if(w[gdzie].dokad[jaki[t[co][gdzie_wco]-'A']]==0)
    {
        w[gdzie].dokad[jaki[t[co][gdzie_wco]-'A']]=nowy;
        nowy++;
        dodaj(co,gdzie_wco-1,nowy-1);
    }
    else dodaj(co,gdzie_wco-1,w[gdzie].dokad[jaki[t[co][gdzie_wco]-'A']]);
}
int szukx,szuky;
string suf;
int wynik=0;
void znajdz(int gdzie_wco,int gdzie)
{
    if(gdzie_wco<0)
    {
        int pocz=0,kon=w[gdzie].Q.size(),sre,ostd=-1;
        while(pocz<kon)
        {
            sre=(pocz+kon)/2;
            if(w[gdzie].Q[sre]<szukx)
                pocz=sre+1;
            else{
                ostd=sre;
                kon=sre;
            }
        }
        int poczz=ostd;
        pocz=0;
        kon=w[gdzie].Q.size(),sre,ostd=-1;
        while(pocz<kon)
        {
            sre=(pocz+kon)/2;
            if(w[gdzie].Q[sre]>szuky)
                kon=sre;
            else{
                ostd=sre;
                pocz=sre+1;
            }
        }
        if(poczz==-1 || ostd==-1)
            return;
        wynik=(ostd-poczz+1);
        return;
    }
    if(w[gdzie].dokad[jaki[suf[gdzie_wco]-'A']]==0)
        return;
    znajdz(gdzie_wco-1,w[gdzie].dokad[jaki[suf[gdzie_wco]-'A']]);
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    jaki['A'-'A']=0;
    jaki['G'-'A']=1;
    jaki['C'-'A']=2;
    jaki['U'-'A']=3;
    w=new wi[2000004];
    int n,m;
    cin>>n>>m;
    string s;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        t[i]=s;
    }
    sort(t,t+n);
    for(int i=0;i<n;i++)
        dodaj(i,t[i].length()-1,1);
    string pref;
    for(int i=1;i<=m;i++)
    {
        cin>>pref>>suf;
        int pocz=0,kon=n,sre,ostd=-1;
        while(pocz<kon)
        {
            sre=(pocz+kon)/2;
            int k=0;
            for(int j=0;j<min(pref.length(),t[sre].length());j++)
            {
                if(pref[j]<t[sre][j])
                {
                    k=1;
                    break;
                }
                if(pref[j]>t[sre][j])
                {
                    k=2;
                    break;
                }
            }
            if(k==2)
                pocz=sre+1;
            else if(k==1)
                kon=sre;
            if(k==0 && t[sre].length()>=pref.length())
            {
                kon=sre;
                ostd=sre;
            }
            if(k==0 && t[sre].length()<pref.length())
                pocz=sre+1;
        }
        int poczz=ostd;
        pocz=0;
        kon=n;
        ostd=-1;
        while(pocz<kon)
        {
            sre=(pocz+kon)/2;
            int k=0;
            for(int j=0;j<min(pref.length(),t[sre].length());j++)
            {
                if(pref[j]<t[sre][j])
                {
                    k=1;
                    break;
                }
                if(pref[j]>t[sre][j])
                {
                    k=2;
                    break;
                }
            }
            if(k==1)
                kon=sre;
            if(k==2)
                pocz=sre+1;
            if(k==0 && pref.length()<=t[sre].length())
            {
                ostd=sre;
                pocz=sre+1;
            }
            if(k==0 && pref.length()>t[sre].length())
                pocz=sre+1;
        }
        if(poczz==-1 || ostd==-1)
        {
            cout<<"0\n";
            continue;
        }
        szukx=poczz;
        szuky=ostd;
        wynik=0;
        znajdz(suf.length()-1,1);
        cout<<wynik<<"\n";
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void znajdz(int, int)':
selling_rna.cpp:45:41: warning: right operand of comma operator has no effect [-Wunused-value]
   45 |         kon=w[gdzie].Q.size(),sre,ostd=-1;
      |                                         ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   95 |             for(int j=0;j<min(pref.length(),t[sre].length());j++)
      |                         ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:128:26: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
  128 |             for(int j=0;j<min(pref.length(),t[sre].length());j++)
      |                         ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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