Submission #444211

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
444211	2021-07-13T11:10:26 Z	Markomafko972	GTA (COI14_gta)	C++14	100 / 100	2353 ms	26944 KB

gta

#include <bits/stdc++.h>
using namespace std;

int n, g;
string t;
map<string, int> bio;
vector<string> v[30];
string pred[30];
map<string, int> gdje;

void solve(string s) {
	if (s.size() > 8 || bio[s] == 1) return;
	bio[s] = 1;
	
	if (s.size() == 4 && pred[g].size() == 0) pred[g] = s;
	gdje[s] = g;

	
	for (int i = 0; i < s.size(); i++) {
		string s2 = "";
		for (int j = 0; j < s.size(); j++) {
			if (i == j) {
				if (s[i] == 'A') {
					s2.push_back('T');
					s2.push_back('C');
				}
				if (s[i] == 'C') {
					s2.push_back('A');
					s2.push_back('G');
				}
				if (s[i] == 'G') {
					s2.push_back('C');
					s2.push_back('T');
				}
				if (s[i] == 'T') {
					s2.push_back('G');
					s2.push_back('A');
				}
			}
			else s2.push_back(s[j]);
		}
		
		if (bio[s2] == 0) solve(s2);
	}
	
	for (int i = 1; i < s.size(); i++) {
		char koji = '?';
		if (s[i-1] == 'T' && s[i] == 'C') koji = 'A';
		if (s[i-1] == 'A' && s[i] == 'G') koji = 'C';
		if (s[i-1] == 'C' && s[i] == 'T') koji = 'G';
		if (s[i-1] == 'G' && s[i] == 'A') koji = 'T';
	
		if (koji != '?') {
			string s2 = "";
			for (int j = 0; j < s.size(); j++) {
				if (j == i-1) {
					s2.push_back(koji);
				}
				else if (j == i) continue;
				else s2.push_back(s[j]);
			}
			
			//cout << "----> " << s2 << endl;
			//system("pause");
			if (bio[s2] == 0) solve(s2);
		}
	}
}

void rek(int x) {
	if (x == 4) {
		if (bio[t] == 1) return;
		//cout << t << ":\n";
		solve(t);
		g++;
		//cout << g << endl;
		return;
	}
	
	t.push_back('A');
	rek(x+1);
	t.pop_back();
	
	t.push_back('C');
	rek(x+1);
	t.pop_back();
	
	t.push_back('G');
	rek(x+1);
	t.pop_back();
	
	t.push_back('T');
	rek(x+1);
	t.pop_back();
}

int grupa[105];

int main () {
	
	rek(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> t;
		while (t.size() > 4) {
			string kraj = "";
			for (int j = 0; j < 5; j++) {
				kraj.push_back(t.back());
				t.pop_back();
			}
			
			reverse(kraj.begin(), kraj.end());
			string dodaj = pred[gdje[kraj]];
			
			for (int j = 0; j < dodaj.size(); j++) t.push_back(dodaj[j]);
		}
		
		grupa[i] = gdje[t];
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (grupa[i] == grupa[j]) cout << 1;
			else cout << 0;
		}
		cout << "\n";
	}
	
	return 0;
}

Compilation message

gta.cpp: In function 'void solve(std::string)':
gta.cpp:19:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for (int i = 0; i < s.size(); i++) {
      |                  ~~^~~~~~~~~~
gta.cpp:21:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for (int j = 0; j < s.size(); j++) {
      |                   ~~^~~~~~~~~~
gta.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int i = 1; i < s.size(); i++) {
      |                  ~~^~~~~~~~~~
gta.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    for (int j = 0; j < s.size(); j++) {
      |                    ~~^~~~~~~~~~
gta.cpp: In function 'int main()':
gta.cpp:116:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |    for (int j = 0; j < dodaj.size(); j++) t.push_back(dodaj[j]);
      |                    ~~^~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	506 ms	26824 KB	Output is correct
2	Correct	494 ms	26680 KB	Output is correct
3	Correct	518 ms	26788 KB	Output is correct
4	Correct	492 ms	26756 KB	Output is correct
5	Correct	512 ms	26772 KB	Output is correct
6	Correct	501 ms	26724 KB	Output is correct
7	Correct	508 ms	26836 KB	Output is correct
8	Correct	512 ms	26796 KB	Output is correct
9	Correct	703 ms	26708 KB	Output is correct
10	Correct	2353 ms	26944 KB	Output is correct