# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
444211 | Markomafko972 | GTA (COI14_gta) | C++14 | 2353 ms | 26944 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.
#include <bits/stdc++.h>
using namespace std;
int n, g;
string t;
map<string, int> bio;
vector<string> v[30];
string pred[30];
map<string, int> gdje;
void solve(string s) {
if (s.size() > 8 || bio[s] == 1) return;
bio[s] = 1;
if (s.size() == 4 && pred[g].size() == 0) pred[g] = s;
gdje[s] = g;
for (int i = 0; i < s.size(); i++) {
string s2 = "";
for (int j = 0; j < s.size(); j++) {
if (i == j) {
if (s[i] == 'A') {
s2.push_back('T');
s2.push_back('C');
}
if (s[i] == 'C') {
s2.push_back('A');
s2.push_back('G');
}
if (s[i] == 'G') {
s2.push_back('C');
s2.push_back('T');
}
if (s[i] == 'T') {
s2.push_back('G');
s2.push_back('A');
}
}
else s2.push_back(s[j]);
}
if (bio[s2] == 0) solve(s2);
}
for (int i = 1; i < s.size(); i++) {
char koji = '?';
if (s[i-1] == 'T' && s[i] == 'C') koji = 'A';
if (s[i-1] == 'A' && s[i] == 'G') koji = 'C';
if (s[i-1] == 'C' && s[i] == 'T') koji = 'G';
if (s[i-1] == 'G' && s[i] == 'A') koji = 'T';
if (koji != '?') {
string s2 = "";
for (int j = 0; j < s.size(); j++) {
if (j == i-1) {
s2.push_back(koji);
}
else if (j == i) continue;
else s2.push_back(s[j]);
}
//cout << "----> " << s2 << endl;
//system("pause");
if (bio[s2] == 0) solve(s2);
}
}
}
void rek(int x) {
if (x == 4) {
if (bio[t] == 1) return;
//cout << t << ":\n";
solve(t);
g++;
//cout << g << endl;
return;
}
t.push_back('A');
rek(x+1);
t.pop_back();
t.push_back('C');
rek(x+1);
t.pop_back();
t.push_back('G');
rek(x+1);
t.pop_back();
t.push_back('T');
rek(x+1);
t.pop_back();
}
int grupa[105];
int main () {
rek(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> t;
while (t.size() > 4) {
string kraj = "";
for (int j = 0; j < 5; j++) {
kraj.push_back(t.back());
t.pop_back();
}
reverse(kraj.begin(), kraj.end());
string dodaj = pred[gdje[kraj]];
for (int j = 0; j < dodaj.size(); j++) t.push_back(dodaj[j]);
}
grupa[i] = gdje[t];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grupa[i] == grupa[j]) cout << 1;
else cout << 0;
}
cout << "\n";
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |