Submission #680111

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
680111	2023-01-09T22:58:46 Z	GusterGoose27	GTA (COI14_gta)	C++11	10 / 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 = 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;

void add_to(vector<string> &nxt, string s) {	
	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 (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 (vis.find(nstr) == vis.end() && nstr.size()) {
				nxt.push_back(nstr);
				vis.insert(nstr);
			}
		}
		it++;
	}
}

void makeable(int i) {
	vis.clear();
	derived[cur].clear();
	derived[cur].push_back(strings[i]);
	it = 0;
	while (it < 2*TIME/n) {
		derived[!cur].clear();
		for (string s: derived[cur]) {
			add_to(derived[!cur], s);
			if (it >= 2*TIME/n) break;
		}
		cur = !cur;
	}
	for (int j = 0; j < i; j++) adj[i][j] = adj[j][i] = (vis.find(strings[j]) != vis.end());
}

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];
		adj[i][i] = 1;
	}
	for (int i = 1; i < n; i++) {
		makeable(i);
	}
	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 'void add_to(std::vector<std::__cxx11::basic_string<char> >&, std::string)':
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: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

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4150 ms	97604 KB	Output is correct
2	Execution timed out	5020 ms	24440 KB	Time limit exceeded
3	Incorrect	4776 ms	8156 KB	Output isn't correct
4	Incorrect	4556 ms	4312 KB	Output isn't correct
5	Incorrect	4662 ms	4528 KB	Output isn't correct
6	Incorrect	4826 ms	4920 KB	Output isn't correct
7	Execution timed out	5018 ms	19248 KB	Time limit exceeded
8	Execution timed out	5032 ms	260568 KB	Time limit exceeded
9	Runtime error	208 ms	262144 KB	Execution killed with signal 9
10	Runtime error	118 ms	262144 KB	Execution killed with signal 9