Submission #680105

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

gta

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 100;
int TIME = 25e6;
string strings[MAXN];
int n;

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

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

int it = 0;

bool add_to(vector<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.push_back(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.push_back(nstr);
				vis.insert(nstr);
			}
		}
		it++;
	}
	return 0;
}

bool makeable(int i, int j) {
	vis.clear();
	derived[cur].clear();
	derived[cur].push_back(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;
			if (it >= 2*TIME/n/n) return 0;
		}
		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::vector<std::__cxx11::basic_string<char> >&, std::string, int)':
gta.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (int i = 0; i < s.size(); i++) {
      |                  ~~^~~~~~~~~~
gta.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i = 0; i < s.size()-1; i++) {
      |                  ~~^~~~~~~~~~~~

Subtask #1

20.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4126 ms	64268 KB	Output is correct
2	Correct	4768 ms	4848 KB	Output is correct
3	Incorrect	4508 ms	716 KB	Output isn't correct
4	Incorrect	4502 ms	588 KB	Output isn't correct
5	Incorrect	4706 ms	600 KB	Output isn't correct
6	Incorrect	4714 ms	484 KB	Output isn't correct
7	Execution timed out	5057 ms	1716 KB	Time limit exceeded
8	Execution timed out	5054 ms	8920 KB	Time limit exceeded
9	Execution timed out	5079 ms	250352 KB	Time limit exceeded
10	Runtime error	115 ms	262144 KB	Execution killed with signal 9