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
#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]);
      |                    ~~^~~~~~~~~~~~~~
# 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