Code Submission Evaluation System Login

HIIT Open 2018

Start:2018-05-26 11:00:00
End:2018-05-26 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2018 - Results
History
2018-05-26 15:56:07
2018-05-26 15:53:54
Task:Letter Game
Sender:Ukkonen Fan Club
Submission time:2018-05-26 15:53:54
Language:C++
Status:READY
Result:ACCEPTED

Test results

testverdicttime (s)
#1ACCEPTED0.01 / 1.00details
#2ACCEPTED0.05 / 1.00details
#3ACCEPTED0.05 / 1.00details
#4ACCEPTED0.05 / 1.00details
#5ACCEPTED0.06 / 1.00details
#6ACCEPTED0.05 / 1.00details
#7ACCEPTED0.05 / 1.00details
#8ACCEPTED0.04 / 1.00details
#9ACCEPTED0.05 / 1.00details
#10ACCEPTED0.04 / 1.00details
#11ACCEPTED0.04 / 1.00details
#12ACCEPTED0.05 / 1.00details
#13ACCEPTED0.05 / 1.00details
#14ACCEPTED0.04 / 1.00details
#15ACCEPTED0.05 / 1.00details
#16ACCEPTED0.05 / 1.00details
#17ACCEPTED0.05 / 1.00details
#18ACCEPTED0.04 / 1.00details
#19ACCEPTED0.04 / 1.00details

Compiler report

input/code.cpp: In function 'int get_enc(std::vector<int>&)':
input/code.cpp:9:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); ++i) {
                 ~~^~~~~~~~~~
input/code.cpp: In function 'int f(int)':
input/code.cpp:65:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < que.size(); ++i) {
                 ~~^~~~~~~~~~~~
input/code.cpp:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < que.size(); ++i) {
                 ~~^~~~~~~~~~~~
input/code.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); ++i) {
                  ~~^~~~~~~~~~
input/code.cpp:83:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i + 1 < v.size(); ++i) {
                  ~~~~~~^~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:157:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); ++i) {
                  ~~^~~~~~~~~~
input/code.cpp:231:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < states.size(); ++i) {
                 ~~^~~~~~~~~~~~~~~
input/code.cpp:240:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ans.size(); ++i) {
                 ~~^~~~~~~~~~~~
input/code.cpp: In function 'int f(int)':
input/code.cpp:132:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Code

#include <bits/stdc++.h>
using namespace std;
const int MN = 1e7;
//A = 0
//B = 1
//. = 2
int get_enc(vector<int> & v) {
	int res = 0;
	for(int i = 0; i < v.size(); ++i) {
		res *= 3;
		res += v[i];
	}
	return res;
}
vector<int> get_vector(int x, int len) {
	vector<int> v(len);
	for(int i = 0; i < len; ++i) {
		v[len-i-1] = x % 3;
		x /= 3;
	}
	return v;
}
int pow(int a, int b) {
	int res = 1;
	for(int i = 0; i < b; ++i) {
		res *= a;
	}
	return res;
}
int visited[MN];
int prv[MN];
int f(int tot_len) {
	if(tot_len <= 2) {
		cout<<"FAIL\n";
		return 0;
	}
	int chars = tot_len-2;
	vector<int> v(tot_len);
	vector<int> que;
	for(int zeros = 0; zeros <= chars; ++zeros) {
		for(int e_pos = 0; e_pos+1 < tot_len; ++e_pos) {
			int c_pos = 0;
			for(int j = 0; j < tot_len; ++j) {
				if(j == e_pos || j == e_pos + 1) {
					v[j] = 2;
				}
				else {
					if(c_pos < zeros) {
						v[j] = 0;
					}
					else {
						v[j] = 1;
					}
					++c_pos;
				}
			}
			//for(auto x: v) cout<<"AB."[x]<<' ';
			//cout<<'\n';
			que.push_back(get_enc(v));
		}
	}
	//cout<<'\n';
	memset(visited, -1, sizeof visited);

	for(int i = 0; i < que.size(); ++i) {
		visited[que[i]] = 0;
		prv[que[i]] = que[i];
		vector<int> v = get_vector(que[i], tot_len);
		//for(auto x: v) cout<<"AB."[x]<<' ';
		//cout<<'\n';
	}
	for(int i = 0; i < que.size(); ++i) {
		vector<int> v = get_vector(que[i], tot_len);
		int dist = visited[que[i]];
		int prev_enc = que[i];
		int em_pos = 0;
		for(int i = 0; i < v.size(); ++i) {
			if(v[i] == 2) {
				em_pos = i;
				break;
			}
		}
		for(int i = 0; i + 1 < v.size(); ++i) {
			if(v[i] != 2 && v[i+1] != 2) {
				swap(v[i], v[em_pos]);
				swap(v[i+1], v[em_pos+1]);
				int enc = get_enc(v);
				if(visited[enc] == -1) {
					prv[enc] = prev_enc;
					visited[enc] = dist+1;
					que.push_back(enc);
				}
				swap(v[i], v[em_pos]);
				swap(v[i+1], v[em_pos+1]);
			}
		}
	}
	/*
	int lim = pow(3, tot_len);
	pair<int, int> ma = {0, 0};
	for(int i = 0; i < lim; ++i) {
		vector<int> v = get_vector(i, tot_len);
		int empty_cnt = 0;
		int a_cnt = 0;
		int b_cnt = 0;
		for(int i = 0; i < v.size(); ++i) {
			if(v[i] == 2) ++empty_cnt;
			if(v[i] == 0) ++a_cnt;
			if(v[i] == 1) ++b_cnt;
		}
		if(empty_cnt != 2 || a_cnt < 2 || b_cnt < 2) continue;
		int ok = 1;
		for(int i = 0; i < v.size(); ++i) {
			if(v[i] == 2 && v[i+1] != 2) {
				ok = 0;
			}
			if(v[i] == 2) break;
		}
		if(!ok) continue;
		if(visited[i] == -1) {
			cout<<"FAIL\n";
			for(auto x: v) cout<<"AB."[x];
			cout<<'\n';
		}
		ma = max(ma, {visited[i], i});
	}
	cout<<ma.first<<endl;
	vector<int> v2 = get_vector(ma.second, tot_len);
	for(auto x: v2) cout<<"AB."[x];
	cout<<'\n';
	*/
}

vector<string> ans;

void move(string& str, int& a, int b) {
	swap(str[a], str[b]);
	swap(str[a+1], str[b+1]);
	ans.push_back(str);
	a = b;
}

int main() {
	int n;
	cin>>n;
	n *= 2;
	string s;
	cin>>s;
	if(n == 2) {
		cout<<0<<'\n';
		return 0;
	}

	int aas = 0;
	int bbs = 0;
	int dots = -1;
	for (int i = 0; i < s.size(); ++i) {
		char c = s[i];
		if (c == 'A') ++aas;
		if (c == 'B') ++bbs;
		if (c == '.' && dots == -1) dots = i;
	}

	int a = 0;
	int b = n - 1;
	
	while(true) {
		if(b - a+1 < 10) break;
		char t = (aas >= 4 ? 'A' : 'B');
		int i1 = (t == 'B' ? -1 : b + 1);
		if(t == 'A') {
			if(dots == a+1) {
				move(s, dots, dots+2);
				move(s, dots, a);
			}
			else if(dots >= a+2) {
				move(s, dots, a);
			}
			for (int i = a; i <= b; ++i) {
				if (s[i] == t) {
					if (t == 'A' && i < i1) i1 = i;
				}
			}	
			move(s, dots, i1);
			++a;
			--aas;
		}
		if(t == 'B') {
			if(dots == b-2) {
				move(s, dots, dots-2);
				move(s, dots, b-1);
			}
			else if(dots <= b-3) {
				move(s, dots, b-1);
			}
			for (int i = a; i <= b; ++i) {
				if (s[i] == t) {
					if (t == 'B' && i1 < i) i1 = i;
				}
			}	
			move(s, dots, i1-1);
			--b;
			--bbs;
		}
	}
	vector<int> v;
	for(int i = a; i <= b; ++i) {
		if(s[i] == 'A') v.push_back(0);
		if(s[i] == 'B') v.push_back(1);
		if(s[i] == '.') v.push_back(2);
	}
	f(b-a+1);
	int pos = get_enc(v);
	if(visited[pos] == -1) {
		cout<<-1<<'\n';
		return 0;
	}
	vector<int> states;
	while(1) {
		vector<int> v2 = get_vector(pos, b-a+1);
		/*
		for(auto x: v2) cout<<"AB."[x];
		cout<<'\n';
		*/
		int next_pos = prv[pos];
		//cout<<next_pos<<'\n';
		if(next_pos == pos) break;
		states.push_back(next_pos);
		pos = next_pos;
	}
	for(int i = 0; i < states.size(); ++i) {
		string s2;
		for(int j = 0; j < a; ++j) s2.push_back('A');
		vector<int> v = get_vector(states[i], b-a+1);
		for(auto x: v) s2.push_back("AB."[x]);
		for(int j = b+1; j < n; ++j) s2.push_back('B');
		ans.push_back(s2);
	}
	cout<<ans.size()<<'\n';
	for(int i = 0; i < ans.size(); ++i) {
		cout<<ans[i]<<'\n';
	}






















	

}

Test details

Test 1

Verdict: ACCEPTED

input
1
..
view   save

correct output
0
view   save

user output
0
view   save

Test 2

Verdict: ACCEPTED

input
2
A..B
view   save

correct output
0
view   save

user output
0
view   save

Test 3

Verdict: ACCEPTED

input
2
B..A
view   save

correct output
-1
view   save

user output
-1
view   save

Test 4

Verdict: ACCEPTED

input
3
AA..BB
view   save

correct output
0
view   save

user output
0
view   save

Test 5

Verdict: ACCEPTED

input
3
AB..AB
view   save

correct output
-1
view   save

user output
-1
view   save

Test 6

Verdict: ACCEPTED

input
3
AB..BA
view   save

correct output
2
ABBA..
A..ABB
view   save

user output
2
ABBA..
A..ABB
view   save

Test 7

Verdict: ACCEPTED

input
3
BA..AB
view   save

correct output
2
..BAAB
AAB..B
view   save

user output
2
..BAAB
AAB..B
view   save

Test 8

Verdict: ACCEPTED

input
3
BA..BA
view   save

correct output
-1
view   save

user output
-1
view   save

Test 9

Verdict: ACCEPTED

input
3
BB..AA
view   save

correct output
2
..BBAA
AABB..
view   save

user output
2
BBAA..
..AABB
view   save

Test 10

Verdict: ACCEPTED

input
100
BBABAABBBAAAAABBBBBBAAAABAAABA...
view   save

correct output
140
..ABAABBBAAAAABBBBBBAAAABAAABA...
AB..AABBBAAAAABBBBBBAAAABAAABA...
ABAA..BBBAAAAABBBBBBAAAABAAABA...
A..ABABBBAAAAABBBBBBAAAABAAABA...
AAB..ABBBAAAAABBBBBBAAAABAAABA...
view   save

user output
388
..ABAABBBAAAAABBBBBBAAAABAAABA...
AB..AABBBAAAAABBBBBBAAAABAAABA...
ABAA..BBBAAAAABBBBBBAAAABAAABA...
A..ABABBBAAAAABBBBBBAAAABAAABA...
AAB..ABBBAAAAABBBBBBAAAABAAABA...
view   save

Test 11

Verdict: ACCEPTED

input
100
AABBABBAAABABBBBBBBBAABABAAAAB...
view   save

correct output
142
AA..ABBAAABABBBBBBBBAABABAAAAB...
AAAB..BAAABABBBBBBBBAABABAAAAB...
AAABBA..AABABBBBBBBBAABABAAAAB...
AAA..ABBAABABBBBBBBBAABABAAAAB...
AAAAB..BAABABBBBBBBBAABABAAAAB...
view   save

user output
388
..BBABBAAABABBBBBBBBAABABAAAAB...
ABBB..BAAABABBBBBBBBAABABAAAAB...
A..BBBBAAABABBBBBBBBAABABAAAAB...
AAABBBB..ABABBBBBBBBAABABAAAAB...
AA..BBBABABABBBBBBBBAABABAAAAB...
view   save

Test 12

Verdict: ACCEPTED

input
100
AAAAABAABBBABAABAAABABBAAAABAA...
view   save

correct output
134
AAAAA..ABBBABAABAAABABBAAAABAA...
AAAAAAB..BBABAABAAABABBAAAABAA...
AAAAAABBB..ABAABAAABABBAAAABAA...
AAAAAA..BBBABAABAAABABBAAAABAA...
AAAAAAABBBB..AABAAABABBAAAABAA...
view   save

user output
389
..AAABAABBBABAABAAABABBAAAABAA...
AA..ABAABBBABAABAAABABBAAAABAA...
AAAB..AABBBABAABAAABABBAAAABAA...
A..BAAAABBBABAABAAABABBAAAABAA...
AAAB..AABBBABAABAAABABBAAAABAA...
view   save

Test 13

Verdict: ACCEPTED

input
100
BBBAAAABAABABAABAABBBABBABABAA...
view   save

correct output
142
..BAAAABAABABAABAABBBABBABABAA...
AAB..AABAABABAABAABBBABBABABAA...
AABAA..BAABABAABAABBBABBABABAA...
AA..ABABAABABAABAABBBABBABABAA...
AAAB..ABAABABAABAABBBABBABABAA...
view   save

user output
388
..BAAAABAABABAABAABBBABBABABAA...
AAB..AABAABABAABAABBBABBABABAA...
A..ABAABAABABAABAABBBABBABABAA...
AAB..AABAABABAABAABBBABBABABAA...
AABAA..BAABABAABAABBBABBABABAA...
view   save

Test 14

Verdict: ACCEPTED

input
100
BABBBAAAAABABAAABBBAABBABABBBB...
view   save

correct output
138
..BBBAAAAABABAAABBBAABBABABBBB...
AABBB..AAABABAAABBBAABBABABBBB...
AA..BBBAAABABAAABBBAABBABABBBB...
AAAABBB..ABABAAABBBAABBABABBBB...
AAAA..BBBABABAAABBBAABBABABBBB...
view   save

user output
385
..BBBAAAAABABAAABBBAABBABABBBB...
AABBB..AAABABAAABBBAABBABABBBB...
A..BBABAAABABAAABBBAABBABABBBB...
AABBB..AAABABAAABBBAABBABABBBB...
AA..BBBAAABABAAABBBAABBABABBBB...
view   save

Test 15

Verdict: ACCEPTED

input
100
ABAAAAABBAAAAAAAAAABABAABBBBBB...
view   save

correct output
126
A..AAAABBAAAAAAAAAABABAABBBBBB...
AAA..AABBAAAAAAAAAABABAABBBBBB...
AAAAA..BBAAAAAAAAAABABAABBBBBB...
AAAAAAABB..AAAAAAAABABAABBBBBB...
AAAAAAA..BBAAAAAAAABABAABBBBBB...
view   save

user output
401
..AAAAABBAAAAAAAAAABABAABBBBBB...
AA..AAABBAAAAAAAAAABABAABBBBBB...
AAAA..ABBAAAAAAAAAABABAABBBBBB...
A..AAAABBAAAAAAAAAABABAABBBBBB...
AAA..AABBAAAAAAAAAABABAABBBBBB...
view   save

Test 16

Verdict: ACCEPTED

input
100
ABBBBBABBABABABBBABAABAAAABBAA...
view   save

correct output
128
A..BBBABBABABABBBABAABAAAABBAA...
AABBBB..BABABABBBABAABAAAABBAA...
AA..BBBBBABABABBBABAABAAAABBAA...
AAABBBBBB..ABABBBABAABAAAABBAA...
AAA..BBBBBBABABBBABAABAAAABBAA...
view   save

user output
479
..BBBBABBABABABBBABAABAAAABBAA...
ABBBBB..BABABABBBABAABAAAABBAA...
A..BBBBBBABABABBBABAABAAAABBAA...
AABBBBBBB..ABABBBABAABAAAABBAA...
AA..BBBBBBBABABBBABAABAAAABBAA...
view   save

Test 17

Verdict: ACCEPTED

input
100
BAAABBABBAAAABABAAABABABBAAABA...
view   save

correct output
139
..AABBABBAAAABABAAABABABBAAABA...
AA..BBABBAAAABABAAABABABBAAABA...
AAABBB..BAAAABABAAABABABBAAABA...
AAA..BBBBAAAABABAAABABABBAAABA...
AAAAABBBB..AABABAAABABABBAAABA...
view   save

user output
387
..AABBABBAAAABABAAABABABBAAABA...
AA..BBABBAAAABABAAABABABBAAABA...
AABB..ABBAAAABABAAABABABBAAABA...
A..BABABBAAAABABAAABABABBAAABA...
AABB..ABBAAAABABAAABABABBAAABA...
view   save

Test 18

Verdict: ACCEPTED

input
100
BBBBBABBAAABBAABBBBBABABABAABA...
view   save

correct output
133
..BBBABBAAABBAABBBBBABABABAABA...
ABBBB..BAAABBAABBBBBABABABAABA...
A..BBBBBAAABBAABBBBBABABABAABA...
AAABBBBB..ABBAABBBBBABABABAABA...
AAA..BBBBBABBAABBBBBABABABAABA...
view   save

user output
386
..BBBABBAAABBAABBBBBABABABAABA...
ABBBB..BAAABBAABBBBBABABABAABA...
A..BBBBBAAABBAABBBBBABABABAABA...
AAABBBBB..ABBAABBBBBABABABAABA...
AA..BBBBABABBAABBBBBABABABAABA...
view   save

Test 19

Verdict: ACCEPTED

input
100
BABBBBBBABBBABBBBBBAABABAAABAA...
view   save

correct output
128
..BBBBBBABBBABBBBBBAABABAAABAA...
ABBBBBBB..BBABBBBBBAABABAAABAA...
A..BBBBBBBBBABBBBBBAABABAAABAA...
AABBBBBBBBBB..BBBBBAABABAAABAA...
AA..BBBBBBBBBBBBBBBAABABAAABAA...
view   save

user output
389
..BBBBBBABBBABBBBBBAABABAAABAA...
ABBBBBBB..BBABBBBBBAABABAAABAA...
A..BBBBBBBBBABBBBBBAABABAAABAA...
AABBBBBBBBBB..BBBBBAABABAAABAA...
AA..BBBBBBBBBBBBBBBAABABAAABAA...
view   save