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

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:20:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=i, k=0; j<str.length() && k<11; j++, k++){
                                  ^
input/code.cpp:65:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<query.length() && found; j++){
                               ^

Code

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0), cout.precision(6);

using namespace std;

class Node{
	public:
		Node* A;
		Node* T;
		Node* C;
		Node* G;		
};

int main(){ _
	string str;
	cin >> str;
	Node* root = new Node();
	for(int i=str.length()-1; i>=0; i--){
		Node* tmp = root;
		for(int j=i, k=0; j<str.length() && k<11; j++, k++){
			
			//if root
			switch(str[j]){
				case 'A': 
					if(tmp->A ==NULL){
						tmp->A = new Node();
						tmp = tmp->A;
					} else {
						tmp = tmp->A;
					}
					break;
				case 'T': 
					if(tmp->T ==NULL){
						tmp->T = new Node();
						tmp = tmp->T;
					} else {
						tmp = tmp->T;
					}
					break;
				case 'C': 
					if(tmp->C ==NULL){
						tmp->C = new Node();
						tmp = tmp->C;
					} else {
						tmp = tmp->C;
					}
					break;
				case 'G': 
					if(tmp->G ==NULL){
						tmp->G = new Node();
						tmp = tmp->G;
					} else {
						tmp = tmp->G;
					}
					break;
			}
		}
	}

	int n; cin >> n;
	for(int i=0; i<n; i++){
		string query; cin >> query;
		Node* tmp = root;
		bool found = true;
		for(int j=0; j<query.length() && found; j++){
			switch(query[j]){
				case 'A': 
					if(tmp->A !=NULL){
						tmp = tmp->A;
					} else {
						found = false;					
					}
					break;
				case 'T': 
					if(tmp->T !=NULL){
						tmp = tmp->T;
					} else {
						found = false;
					}
					break;
				case 'C': 
					if(tmp->C !=NULL){
						tmp = tmp->C;
					} else {
						found = false;
					}
					break;
				case 'G': 
					if(tmp->G !=NULL){
						tmp = tmp->G;
					} else {
						found = false;
					}
					break;
			}
		}
		if(found) { cout << "YES" << endl; }
		else { cout << "NO" << endl; }
	}

	return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
ACGCGGGCTCCTAGCGTTAGCAGTTGAGTG...

correct output
YES
YES
NO
NO
YES
...

user output
YES
YES
NO
NO
YES
...