# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
680112 | GusterGoose27 | GTA (COI14_gta) | C++11 | 5063 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 = 5e6;
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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |