Submission #156319

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
156319	2019-10-05T05:38:39 Z	socho	GTA (COI14_gta)	C++14	50 / 100	4655 ms	36492 KB

gta

#include "bits/stdc++.h"
using namespace std;
 
string g = "ACGT";
 
int TRUNCATE = 8;
 
int gp(char a, char b) {
	if (a == 'T' && b == 'C') return 0;
	if (a == 'A' && b == 'G') return 1;
	if (a == 'C' && b == 'T') return 2;
	if (a == 'G' && b == 'A') return 3;
	return 4;
}
 
string sh(string s) {
	stack<char> c;
	for (int i=0; i<s.size(); i++) {
		c.push(s[i]);
		bool can = true;
		while (c.size() > 1 && can) {
			char t = c.top(); c.pop(); char nx = c.top(); c.push(t);
			int res = gp(nx, t);
			if (res == 4) can = false;
			else {
				c.pop();
				c.pop();
				c.push(g[res]);
			}
		}
	}
	
	string ge;
	stack<char> f;
	while (!c.empty()) {
		f.push(c.top());
		c.pop();
	}
	while (!f.empty()) {
		ge += f.top();
		f.pop();
	}
	return ge;
	
	
}
 
vector<string> r;
 
map<string, string> par;
 
string parent(string s) {
	if (par[s] == s) return s;
	return par[s] = parent(par[s]);
}
 
bool arc(string a, string b) {
	// cout << parent(a) << ' ' << parent(b) << endl;
	return parent(a) == parent(b);
}
 
void connect(string a, string b) {
	if (arc(a, b)) return;
	string ax = parent(a);
	string bx = parent(b);
	par[ax] = bx;
}
 
vector<string> gwi(int n) {
	if (n == 0) {
		return r;
	}
	vector<string> rs;
	vector<string> las = gwi(n-1);
	for (int j=0; j<las.size(); j++) {
		for (int i=0; i<4; i++) {
			string cons = las[j] + g[i];
			par[cons] = cons;
			// cout << cons << endl;
			rs.push_back(cons);
		}
		rs.push_back(las[j]);
	}
	return rs;
	
}
 
map<char, string> inv;
 
void proc(string s) {
	if (s.size() >= TRUNCATE) return;
	for (int i=0; i<s.size(); i++) {
		string c = "";
		for (int j=0; j<i; j++) c += s[j];
		c += inv[s[i]];
		for (int j=i+1; j<s.size(); j++) c += s[j];
		// cout << "! " << s << ' ' << c << endl;
		connect(s, c);
	}
}
 
int main() {
	
	inv['A'] = "TC";
	inv['C'] = "AG";
	inv['G'] = "CT";
	inv['T'] = "GA";
	
	int n;
	cin >> n;
	vector<string> grid;
	for (int i=0; i<n; i++) {
		string s;
		cin >> s;
		string result = sh(s);
		par[result] = result;
		grid.push_back(result);
	}
	
	r.push_back("");
	vector<string> all = gwi(TRUNCATE);
	// cout << all.size() << endl;
	
	for (int i=0; i<all.size(); i++) {
		proc(all[i]);
	}
	
	for (int i=0; i<grid.size(); i++) {
		for (int j=0; j<grid.size(); j++) {
			cout << arc(grid[i], grid[j]);
		}
		cout << endl;
	}
	
	
}

Compilation message

gta.cpp: In function 'std::__cxx11::string sh(std::__cxx11::string)':
gta.cpp:18:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<s.size(); i++) {
                ~^~~~~~~~~
gta.cpp: In function 'std::vector<std::__cxx11::basic_string<char> > gwi(int)':
gta.cpp:75:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j=0; j<las.size(); j++) {
                ~^~~~~~~~~~~
gta.cpp: In function 'void proc(std::__cxx11::string)':
gta.cpp:91:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (s.size() >= TRUNCATE) return;
      ~~~~~~~~~^~~~~~~~~~~
gta.cpp:92:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<s.size(); i++) {
                ~^~~~~~~~~
gta.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=i+1; j<s.size(); j++) c += s[j];
                   ~^~~~~~~~~
gta.cpp: In function 'int main()':
gta.cpp:124:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<all.size(); i++) {
                ~^~~~~~~~~~~
gta.cpp:128:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<grid.size(); i++) {
                ~^~~~~~~~~~~~
gta.cpp:129:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<grid.size(); j++) {
                 ~^~~~~~~~~~~~

Subtask #1

50.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3828 ms	27960 KB	Output is correct
2	Correct	3840 ms	27856 KB	Output is correct
3	Correct	3830 ms	28032 KB	Output is correct
4	Correct	3885 ms	27948 KB	Output is correct
5	Correct	3839 ms	27904 KB	Output is correct
6	Incorrect	3935 ms	27900 KB	Output isn't correct
7	Incorrect	3936 ms	27904 KB	Output isn't correct
8	Incorrect	4059 ms	28032 KB	Output isn't correct
9	Incorrect	4090 ms	28672 KB	Output isn't correct
10	Incorrect	4655 ms	36492 KB	Output isn't correct