Submission #680092

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
680092	2023-01-09T22:34:29 Z	GusterGoose27	GTA (COI14_gta)	C++11	20 / 100	5000 ms	262144 KB

gta

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 100;
int TIME = 1e7;
string strings[MAXN];
int n;

set<string> vis;
bool adj[MAXN][MAXN];
set<string> derived[2];
bool cur = 0;

map<char, string> conv;
map<string, string> conv2;

int it = 0;

bool add_to(set<string> &nxt, string s, int j) {	
	for (int i = 0; i < s.size(); i++) {
		string nstr = s.substr(0, i)+conv[s[i]]+s.substr(i+1, s.size()-i-1);
		if (nstr == strings[j]) {
			return 1;
		}
		if (vis.find(nstr) == vis.end() && nstr.size()) {
			nxt.insert(nstr);
			vis.insert(nstr);
		}
		it++;
	}
	for (int i = 0; i < s.size()-1; i++) {
		string seq = s.substr(i, 2);
		if (conv2.find(seq) != conv2.end()) {
			string nstr = s.substr(0, i)+conv2[seq]+s.substr(i+2, s.size()-i-2);
			if (nstr == strings[j]) {
				return 1;
			}
			if (vis.find(nstr) == vis.end() && nstr.size()) {
				nxt.insert(nstr);
				vis.insert(nstr);
			}
		}
		it++;
	}
	return 0;
}

bool makeable(int i, int j) {
	vis.clear();
	derived[cur].clear();
	derived[cur].insert(strings[i]);
	it = 0;
	while (it < 2*TIME/n/n) {
		derived[!cur].clear();
		for (string s: derived[cur]) {
			if (add_to(derived[!cur], s, j)) return 1;
		}
		cur = !cur;
	}
	return 0;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	conv['A'] = "TC";
	conv['C'] = "AG";
	conv['G'] = "CT";
	conv['T'] = "GA";
	conv2["TC"] = "A";
	conv2["AG"] = "C";
	conv2["CT"] = "G";
	conv2["GA"] = "T";
	for (int i = 0; i < n; i++) {
		cin >> strings[i];
		for (int j = 0; j < i; j++) {
			adj[i][j] = adj[j][i] = makeable(j, i);
		}
		adj[i][i] = 1;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) cout << adj[i][j];
		cout << "\n";
	}
}

Compilation message

gta.cpp: In function 'bool add_to(std::set<std::__cxx11::basic_string<char> >&, std::string, int)':
gta.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int i = 0; i < s.size(); i++) {
      |                  ~~^~~~~~~~~~
gta.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for (int i = 0; i < s.size()-1; i++) {
      |                  ~~^~~~~~~~~~~~

Subtask #1

20.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3964 ms	78000 KB	Output is correct
2	Correct	4280 ms	4252 KB	Output is correct
3	Incorrect	3156 ms	564 KB	Output isn't correct
4	Incorrect	4612 ms	476 KB	Output isn't correct
5	Execution timed out	5068 ms	604 KB	Time limit exceeded
6	Incorrect	3475 ms	468 KB	Output isn't correct
7	Execution timed out	5088 ms	2648 KB	Time limit exceeded
8	Runtime error	474 ms	262144 KB	Execution killed with signal 9
9	Execution timed out	5087 ms	250396 KB	Time limit exceeded
10	Runtime error	112 ms	262144 KB	Execution killed with signal 9