QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#331757 | #8058. Binary vs Ternary | ucup-team197# | WA | 2ms | 3624kb | C++20 | 4.0kb | 2024-02-18 18:46:09 | 2024-02-18 18:46:09 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <array>
#include <map>
#include <set>
#include <numeric>
#include <vector>
#include <string>
using namespace std;
string a, b;
vector<pair<int, int>> ans;
int cnt_1_a = 0;
int cnt_1_b = 0;
int leading_a, leading_b;
void output(){
cout << ans.size() << "\n";
for(auto [l, r]: ans)
cout << l << " " << r << "\n";
ans.clear();
}
void turn_11(){
int pos = -1;
for(int i = a.size() - 2; i >= 0; --i){
if(a[i] == '1' && a[i + 1] == '1'){
pos = i;
break;
}
if(a[i] == '1' && a[i + 1] == '0'){
ans.push_back({i + 1, i + 2});
a[i + 1] = '1';
pos = i;
break;
}
}
if(pos == -1){
cout << "-1\n";
return;
}
while(a.size() > pos + 2){
if(a[pos + 2] == '0'){
ans.push_back({pos + 1 + 1, pos + 2 + 1});
a[pos + 2] = '1';
}
ans.push_back({pos + 1, pos + 2});
ans.push_back({pos + 2, pos + 4});
a.erase(a.begin() + pos + 2);
}
while(pos != leading_a){
if(a[pos - 1] == '0'){
ans.push_back({pos, pos + 1});
a.erase(a.begin() + pos - 1);
--pos;
continue;
}
ans.push_back({pos, pos + 1});
ans.push_back({pos + 1, pos + 3});
a.erase(a.begin() + pos - 1);
--pos;
}
}
void expand(){
int pos = leading_a;
for(int i = b.size() - 1; i >= leading_b + 1; --i){
if(b[i] == '1'){
ans.push_back({pos + 1, pos + 2});
ans.push_back({pos + 1, pos + 2});
ans.push_back({pos + 2, pos + 3});
}
else{
ans.push_back({pos + 1, pos + 2});
ans.push_back({pos + 1, pos + 2});
}
}
if(b.size() == leading_b) return;
if(b[leading_b] == '1'){
ans.push_back({pos + 1, pos + 2});
ans.push_back({pos + 2, pos + 4});
}
else{
ans.push_back({pos + 1, pos + 2});
ans.push_back({pos + 2, pos + 4});
}
output();
}
void solve_real(){
leading_a = 0, leading_b = 0;
{
for(int i = 0; i < a.size(); ++i){
if(a[i] == '1') break;
leading_a = i + 1;
}
for(int i = 0; i < b.size(); ++i){
if(b[i] == '1') break;
leading_b = i + 1;
}
if(leading_a < leading_b){
cout << "-1\n";
return;
}
ans.push_back({1, leading_a - leading_b + 1});
a.erase(0, leading_a - leading_b);
leading_a = leading_b;
}
// cout << "turn 11" << endl;
turn_11();
// cout << endl << a << " " << b << " a b" << endl;
// cout << "expand" << endl;
expand();
// cout << endl << a << " " << b << "after" << endl;
// cout << "after" << endl;
}
void solve(){
cin >> a >> b;
ans.clear();
cnt_1_a = cnt_1_b = 0;
for(char c: a)
cnt_1_a += c == '1';
for(char c: b)
cnt_1_b += c == '1';
if(!cnt_1_a){
if(cnt_1_b || b.size() > a.size()){
cout << "-1\n";
return;
}
while(a.size() > b.size()){
ans.push_back({a.size() - 1, a.size()});
a.pop_back();
}
output();
return;
}
if(!cnt_1_b){
cout << "-1\n";
return;
}
if(cnt_1_a == 1 && a.back() == '1'){
if(cnt_1_b != cnt_1_a || b.back() != '1' || b.size() > a.size()){
cout << "-1\n";
return;
}
while(a.size() > b.size()){
ans.push_back({1, 2});
a.pop_back();
a.pop_back();
a += "1";
}
output();
return;
}
solve_real();
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3624kb
input:
3 1 111 110110 1101010 1111 111111
output:
-1 26 1 1 5 6 4 5 5 7 3 4 2 3 3 5 1 2 2 4 1 2 1 2 1 2 1 2 2 3 1 2 1 2 1 2 1 2 2 3 1 2 1 2 1 2 1 2 2 3 1 2 2 4 22 1 1 2 3 3 5 1 2 2 4 1 2 1 2 2 3 1 2 1 2 2 3 1 2 1 2 2 3 1 2 1 2 2 3 1 2 1 2 2 3 1 2 2 4
result:
ok Haitang Suki (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 3616kb
input:
1000 11100 111 1 11110 10001 10 1011 1111 10 1110 1100 11 11010 11 110 11 1 10001 10110 10 10 11111 10000 1001 10 1 11 10111 11 10 1 100 11 10100 1 10 101 11 1100 110 11 1110 1 1001 1 11111 10 10010 10 11001 110 1010 10011 1110 10100 1001 1001 101 100 1 1001 11 101 11 101 1001 1 1 1011 1 10 10 1011 ...
output:
17 1 1 3 4 4 5 3 4 4 6 2 3 3 5 1 2 2 4 1 2 1 2 2 3 1 2 1 2 2 3 1 2 2 4 -1 14 1 1 1 2 2 3 1 2 2 4 2 3 1 2 2 4 1 2 2 4 1 2 1 2 1 2 2 4 15 1 1 2 3 1 2 2 4 1 2 1 2 2 3 1 2 1 2 2 3 1 2 1 2 2 3 1 2 2 4 12 1 1 1 2 1 2 1 2 1 2 1 2 2 3 1 2 1 2 2 3 1 2 2 4 12 1 1 2 3 3 4 2 3 3 5 1 2 2 4 1 2 1 2 2 3 1 2 2 4 12...
result:
wrong answer (l,r) is invalid (test case 13)