QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #658212 | #8058. Binary vs Ternary | ucup-team4992# | WA | 1ms | 3588kb | C++20 | 3.3kb | 2024-10-19 16:23:41 | 2024-10-19 16:23:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1000+5;
string str1,str2;
vector<pair<int,int>>ans;
int num[N],tot,pos[N],sum[N];
int n,m;
void init(string str, int &pre, int &kind){
int len=str.length()-1;
for(int i=1; i<=len; i++){
if(str[i]=='0') pre++;
else{
kind=(i<len-1 ? 3 : 2);
return;
}
}
kind=1;
return;
}
void solve2(int pre1, int pre2){
if(pre1>pre2){
ans.push_back(make_pair(1,pre1-pre2+1));
pre1=pre2;
}
}
void solve(){
ans.clear(); tot=0;
cin>>str1>>str2;
n=str1.length(); m=str2.length();
str1=" "+str1; str2=" "+str2;
int pre1=0,pre2=0;
int kind1=0,kind2=0;
init(str1,pre1,kind1);
init(str2,pre2,kind2);
if(pre1<pre2 || kind1!=kind2){
cout<<"-1\n";
return;
}
if(kind1==1 || kind1==2) solve2(pre1,pre2);
else{
int minus=0;
tot=0;
for(int i=pre2+1; i<=m; i++){
if(str2[i]=='1' || str2[i]!=str2[i-1]){
tot++;
pos[tot]=i;
num[tot]=str2[i];
sum[tot]=1;
}else{
sum[tot]++;
}
}
// for(int i=1; i<=tot; i++) cout<<pos[i]<<" , "<<num[i]<<" , "<<sum[i]<<"\n";
int st=-1;
int cnt=0;
for(int i=pre1+1; i<=n; i++){
if(str1[i]=='0'){
if(st==-1) st=i;
}else{
if(st!=-1){
ans.push_back(make_pair(st-minus,i-minus));
minus+=i-st;
st=-1;
}
cnt++;
}
}
if(st!=-1){
if(st!=n) ans.push_back(make_pair(st-minus,n-minus));
ans.push_back(make_pair(st-minus-1,st-minus));
cnt++;
}
// cout<<"cnt = "<<cnt<<"\n";
pre1++; pre2++;
while(cnt>tot){
ans.push_back(make_pair(pre1,pre1+1));
if(cnt>2) ans.push_back(make_pair(pre1+1,pre1+3));
else{
ans.push_back(make_pair(pre1+1,pre1+2));
ans.push_back(make_pair(pre1,pre1+1));
}
cnt--;
}
while(cnt<tot){
ans.push_back(make_pair(pre1,pre1+1));
ans.push_back(make_pair(pre1,pre1+1));
ans.push_back(make_pair(pre1+1,pre1+2));
cnt++;
}
pre1--; pre2--;
for(int i=tot; i>=2; i--){
if(num[i]=='0'){
ans.push_back(make_pair(pre1+i-1,pre1+i));
if(sum[i]==1){
ans.push_back(make_pair(pre1+i,pre1+i+1));
}else{
int cnt=2;
while(cnt<sum[i]){
ans.push_back(make_pair(pre1+i-1,pre1+i));
ans.push_back(make_pair(pre1+i-1,pre1+i));
cnt++;
}
}
}
}
solve2(pre1,pre2);
cout<<ans.size()<<"\n";
for(auto x:ans) cout<<x.first<<" "<<x.second<<"\n";
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T=1;
cin>>T;
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3588kb
input:
3 1 111 110110 1101010 1111 111111
output:
-1 14 3 4 4 5 1 2 1 2 2 3 1 2 1 2 2 3 6 7 7 8 4 5 5 6 2 3 3 4 6 1 2 1 2 2 3 1 2 1 2 2 3
result:
ok Haitang Suki (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3564kb
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:
4 4 5 3 4 1 2 2 4 -1 -1 4 2 3 1 2 1 2 2 3 -1 -1 -1 -1 -1 -1 -1 6 2 5 1 2 1 2 1 2 2 3 1 2 -1 -1 -1 -1 4 3 4 2 3 2 3 3 4 -1 -1 -1 -1 -1 8 2 3 1 2 1 2 2 3 3 4 4 5 1 2 2 3 6 2 4 1 2 1 2 2 3 3 4 4 5 4 2 3 3 4 2 3 1 2 6 2 4 1 2 1 2 2 3 1 2 2 3 -1 -1 -1 5 2 3 1 2 1 2 2 3 1 2 -1 -1 8 4 5 1 2 1 2 2 3 4 5 5 6...
result:
wrong answer Pans=-1, Jans!=-1 (test case 3)