Submission #680101

# Submission time Handle Problem Language Result Execution time Memory
680101 2023-01-09T22:46:37 Z GusterGoose27 GTA (COI14_gta) C++11
20 / 100
5000 ms 262144 KB
#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 = 1e7;
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;
		}
		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 = 7*TIME/5;
		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++) {
      |                  ~~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 2607 ms 55652 KB Output is correct
2 Correct 3134 ms 3952 KB Output is correct
3 Execution timed out 5071 ms 1180 KB Time limit exceeded
4 Incorrect 3299 ms 468 KB Output isn't correct
5 Execution timed out 5062 ms 724 KB Time limit exceeded
6 Incorrect 2694 ms 460 KB Output isn't correct
7 Execution timed out 5038 ms 2488 KB Time limit exceeded
8 Runtime error 321 ms 262144 KB Execution killed with signal 9
9 Execution timed out 5076 ms 249428 KB Time limit exceeded
10 Runtime error 118 ms 262144 KB Execution killed with signal 9