# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
680105 | GusterGoose27 | GTA (COI14_gta) | C++11 | 5079 ms | 262144 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |