Submission #680097

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
680097	2023-01-09T22:41:55 Z	GusterGoose27	GTA (COI14_gta)	C++11	0 / 100	5000 ms	1616 KB

gta

#pragma GCC optimize("Ofast")

#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() && nstr.size() < 6) {
			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() && nstr.size() < 6) {
				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];
		if (i == 0 && strings[i].size() == 3) TIME = 3*TIME/2;
		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:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int i = 0; i < s.size(); i++) {
      |                  ~~^~~~~~~~~~
gta.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for (int i = 0; i < s.size()-1; i++) {
      |                  ~~^~~~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	5080 ms	212 KB	Time limit exceeded
2	Execution timed out	5088 ms	212 KB	Time limit exceeded
3	Execution timed out	5097 ms	212 KB	Time limit exceeded
4	Execution timed out	5095 ms	212 KB	Time limit exceeded
5	Execution timed out	5091 ms	212 KB	Time limit exceeded
6	Execution timed out	5094 ms	212 KB	Time limit exceeded
7	Execution timed out	5098 ms	212 KB	Time limit exceeded
8	Execution timed out	5088 ms	340 KB	Time limit exceeded
9	Execution timed out	5098 ms	584 KB	Time limit exceeded
10	Execution timed out	5098 ms	1616 KB	Time limit exceeded