QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #306899 | #8058. Binary vs Ternary | installb# | WA | 2ms | 3628kb | C++14 | 2.7kb | 2024-01-17 15:32:23 | 2024-01-17 15:32:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000005;
int a[N];
string trans(string x){
if(x == "00") return "0";
if(x == "01") return "1";
if(x == "10") return "11";
if(x == "11") return "100";
assert(0);
}
void solve(){
string s,t;
vector <pair <int,int> > ans;
cin >> s; cin >> t;
string ss = s;
if(s.length() == 1){
if(s == t) cout << 0 << '\n';
else cout << -1 << '\n';
return;
}
// A -> 111...111
for(int i = 1;i < s.length();i ++){
if(s[i] == '0'){
ans.push_back({i - 1,i});
s[i] = '1';
// 10 -> 11
}
}
int cb1 = 0;
for(int i = 0;i < t.length();i ++) if(t[i] == '1') cb1 ++;
// modify A length
if(cb1 > s.length()){
while(s.length() < cb1){
ans.push_back({s.length() - 2,s.length() - 1}); s[s.length() - 1] = '0'; s += '0'; // 11 -> 100 -> 111
ans.push_back({s.length() - 3,s.length() - 2}); s[s.length() - 2] = '1';
ans.push_back({s.length() - 2,s.length() - 1}); s[s.length() - 1] = '1';
}
}
if(cb1 < s.length()){
while(s.length() > max(2,cb1)){
ans.push_back({0,1}); // 111 -> 1001 -> 11
ans.push_back({2,3});
ans.push_back({1,2});
s.pop_back();
}
}
if(cb1 == 1){
// s == "11"
ans.push_back({0,1});
ans.push_back({1,2});
// s == "10";
while(s.length() < t.length()){
ans.push_back({0,1});
ans.push_back({0,1});
s += '0';
}
}
else{
int cur = 0;
for(int i = 0;i < t.length();i ++){
if(t[i] == '1'){
cur ++;
a[cur] = 0;
}
if(t[i] == '0') a[cur] ++;
}
for(int j = s.length() - 1;j >= 1;j --){
for(int k = 1;k <= a[j + 1];k ++){
ans.push_back({j - 1,j});
ans.push_back({j - 1,j});
}
}
}
if(a[1]){
ans.push_back({0,1});
ans.push_back({0,1});
ans.push_back({1,2});
ans.push_back({0,1});
ans.push_back({1,2});
for(int i = 2;i <= a[1];i ++){
ans.push_back({0,1});
ans.push_back({0,1});
}
}
cout << ans.size() << '\n';
for(auto [x,y] : ans){
cout << x + 1 << ' ' << y + 1 << '\n';
// ss = ss.substr(0,x) + trans(ss.substr(x,y - x + 1)) + ss.substr(y + 1,ss.length());
// cout << ss << '\n';
}
}
int main(){
ios::sync_with_stdio(false);
int TC; cin >> TC;
while(TC --) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
input:
3 1 111 110110 1101010 1111 111111
output:
-1 14 2 3 5 6 1 2 3 4 2 3 1 2 3 4 2 3 3 4 3 4 2 3 2 3 1 2 1 2 6 3 4 3 4 4 5 4 5 4 5 5 6
result:
ok Haitang Suki (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 3604kb
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:
8 3 4 4 5 1 2 3 4 2 3 1 2 3 4 2 3 -1 14 1 2 2 3 3 4 1 2 3 4 2 3 1 2 3 4 2 3 1 2 3 4 2 3 1 2 2 3 1 1 2 6 1 2 1 2 1 2 2 3 2 3 2 3 8 2 3 3 4 1 2 3 4 2 3 1 2 3 4 2 3 11 2 3 4 5 1 2 3 4 2 3 1 2 3 4 2 3 1 2 3 4 2 3 4 2 3 1 2 3 4 2 3 -1 13 1 2 4 5 1 2 3 4 2 3 1 2 3 4 2 3 1 2 3 4 2 3 1 2 2 3 10 1 2 1 2 1 2 ...
result:
wrong answer (l,r) is invalid (test case 13)