CSES - HIIT Open 2016 - Results
Submission details
Task:DNA sequence
Sender:zah
Submission time:2016-05-28 14:53:39 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.07 sdetails

Code

#include <iostream>
#include <map>

using namespace std;



int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string dna;
    cin >> dna;
    int n=dna.size();
    int DNA[n];
    map<char,int> m;
    m['A']=4; m['C']=1; m['T']=2; m['G']=3;    
    short int t[1<<21]={};
    for (int i=0; i<n; ++i){
        DNA[i]=m[dna[i]];
    }
    for(int i=0; i<n; ++i){
        int h=0;
        for (int j=0; j<min(10, n-i-1); ++j){
            h+=DNA[i+j];
            t[h]=1;
            h*=4;
        }
        
            
    }
    int q;
    cin >> q;
    for(int i=0; i<q; ++i){
        string sas; 
        cin >> sas;
        int s=sas.size();
        int h=0;
        int ff=1;
        for (int j=0; j<min(s,10);++j){
            h+=m[sas[j]];
            if (t[h]==0){
                ff=0;
                break;
            }
            h*=4;      
        } 
        if (ff) cout << "YES\n";
        else cout << "NO\n";
    }

}

Test details

Test 1

Verdict: ACCEPTED

input
ACGCGGGCTCCTAGCGTTAGCAGTTGAGTG...

correct output
YES
YES
NO
NO
YES
...

user output
YES
YES
NO
NO
YES
...