QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #217689 | #6683. Difficult Constructive Problem | zzwtx | AC ✓ | 2ms | 4008kb | C++14 | 4.6kb | 2023-10-17 10:07:59 | 2023-10-17 10:07:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,k;
char s[100005],a[100005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1,T0=0;
cin>>T;
while(++T0<=T){
cin>>n>>k;
k++;
cin>>s+1;
/*if(T0==4547){
cout<<1<<' '<<n<<' '<<k-1<<' ';
for(int i=1;i<=n;i++)
cout<<s[i];
cout<<'\n';
}*/
int k0=0;
for(int i=1;i<=n;i++){
a[i]=s[i]=='?'?'0':s[i];
if(a[i]!=a[i-1]) k0++;
}
int c=k-k0;
//cout<<c<<'\n';
bool Im=true;
if((c>0?c:-c)&1){
Im=false;
char sc[100005];
int cc=c;
for(int i=1;i<=n;i++) sc[i]=a[i];
bool ff=false;
if(n>1&&s[n]=='?'&&a[n]!=a[n-1]){
a[n]='1';
c++;
ff=true;
}else if(n>1&&s[n]=='?'&&a[n]==a[n-1]){
a[n]='1';
c--;
ff=true;
}
if(!ff){
Im=true;
}
if(!Im){
a[n+1]=0;
for(int i=n-1;i>1;i--){
if(s[i]=='?'){
//cout<<c<<'\n';
if(i>1&&i<n&&a[i-1]!=a[i+1])
continue;
if(a[i+1]==a[i]&&c>0){
a[i]='1';
c-=2;
}/*else if(a[i+1]!=a[i]&&c<0){
a[i]='1';
c+=2;
}*/
}
}
if(c<0){
for(int i=n-1;i>1;i--){
if(c<=-2&&s[i]=='?'&&a[i]!=a[i+1]){
int j;
for(j=i;s[j]=='?'&&a[j]==a[i];j--);
if(a[j]==a[i+1]){
for(int k=j+1;k<=i;k++){
a[k]='1';
}
c+=2;
}
}
}
}
if(c==0)
cout<<a+1<<'\n';
else{
bool f=false;
if(c==2&&n>2&&s[1]=='?'&&s[n]=='?'){
int j;
for(j=1;a[j]!=a[j+1]&&s[j]=='?'&&s[j+1]=='?';j++);
if(a[j]==a[j+1]){
for(int k=1;k<=j;k++){
a[k]=((a[k]-'0')^1)+'0';
}
f=true;
}else f=false;
if(f){
for(j=n;a[j]!=a[j-1]&&s[j]=='?'&&s[j-1]=='?';j--);
if(a[j]==a[j-1]){
for(int k=n;k>=j;k--){
a[k]=((a[k]-'0')^1)+'0';
}
f=true;
}else f=false;
}
if(f) cout<<a+1<<'\n';
}else if(c==-2&&n>2&&s[1]=='?'&&s[n]=='?'){
int j;
for(j=2;a[j]==a[1]&&s[j]=='?';j++);
if(a[j]!=a[1]){
for(int k=1;k<j;k++){
a[k]=((a[k]-'0')^1)+'0';
}
f=true;
}else f=false;
if(f){
for(j=n-1;a[j]==a[n]&&s[j]=='?';j--);
if(a[j]!=a[n]){
for(int k=n;k>j;k--){
a[k]=((a[k]-'0')^1)+'0';
}
f=true;
}else f=false;
}
if(f) cout<<a+1<<'\n';
}
if(!f) Im=true;
}
}
for(int i=1;i<=n;i++) a[i]=sc[i];
c=cc;
//cout<<c<<'\n';
if(Im){
if(n>1&&s[1]=='?'&&a[1]!=a[2]){
a[1]='1';
c++;
ff=true;
}else if(n>1&&s[1]=='?'&&a[1]==a[2]){
a[1]='1';
c--;
ff=true;
}
}
if(!ff){
//cout<<"???";
cout<<"Impossible\n";
continue;
}
}
if(Im){
//cout<<c<<'\n';
a[n+1]=0;
for(int i=n-1;i>1;i--){
if(s[i]=='?'){
//cout<<c<<'\n';
if(i>1&&i<n&&a[i-1]!=a[i+1])
continue;
if(a[i+1]==a[i]&&c>0){
a[i]='1';
c-=2;
}/*else if(a[i+1]!=a[i]&&c<0){
a[i]='1';
c+=2;
}*/
}
}
if(c<0){
//cout<<a+1<<'\n';
for(int i=n-1;i>1;i--){
if(c<=-2&&s[i]=='?'&&a[i]!=a[i+1]){
//cout<<i<<'\n';
int j;
for(j=i;s[j]=='?'&&a[j]==a[i];j--);
if(a[j]==a[i+1]){
for(int k=j+1;k<=i;k++){
a[k]='1';
}
c+=2;
}
}
}
}
if(c==0)
cout<<a+1<<'\n';
else{
bool f=false;
if(c==2&&n>2&&s[1]=='?'&&s[n]=='?'){
//cout<<a+1<<' '<<"T1\n";
int j;
for(j=1;a[j]!=a[j+1]&&s[j]=='?'&&s[j+1]=='?';j++);
if(a[j]==a[j+1]){
for(int k=1;k<=j;k++){
a[k]=((a[k]-'0')^1)+'0';
}
f=true;
}else f=false;
if(f){
for(j=n;a[j]!=a[j-1]&&s[j]=='?'&&s[j-1]=='?';j--);
if(a[j]==a[j-1]){
for(int k=n;k>=j;k--){
a[k]=((a[k]-'0')^1)+'0';
}
f=true;
}else f=false;
}
if(f) cout<<a+1<<'\n';
}else if(c==-2&&n>2&&s[1]=='?'&&s[n]=='?'){
int j;
for(j=2;a[j]==a[1]&&s[j]=='?';j++);
if(a[j]!=a[1]){
for(int k=1;k<j;k++){
a[k]=((a[k]-'0')^1)+'0';
}
f=true;
}else f=false;
if(f){
for(j=n-1;a[j]==a[n]&&s[j]=='?';j--);
if(a[j]!=a[n]){
for(int k=n;k>j;k--){
a[k]=((a[k]-'0')^1)+'0';
}
f=true;
}else f=false;
}
if(f) cout<<a+1<<'\n';
}
if(!f){
//cout<<a+1<<' '<<c<<'\n';
cout<<"Impossible\n";
}
}
}
}
return 0;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3768kb
input:
5 9 6 1?010??01 9 5 1?010??01 9 6 100101101 9 5 100101101 9 3 ????????1
output:
100100101 Impossible 100101101 Impossible 000000101
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 4008kb
input:
6110 2 0 01 9 5 ????110?? 18 8 ???111???00??010?? 11 8 001??01???0 2 0 00 8 1 ?????111 11 2 110???01??? 13 7 ??100???01??1 6 2 ?????0 18 8 110??11??011??110? 12 5 00??011??00? 20 10 ??01???0011???0010?? 1 0 ? 13 6 ???10??110??0 6 2 00???1 17 10 ??010??001???11?? 5 2 ????0 14 7 010???00???11? 2 1 01 ...
output:
Impossible 001011001 000111000000101010 00101010010 00 00000111 11000001111 0010000101001 000010 110001100011001101 000001101001 00010000011001001010 0 0001000110010 Impossible 00010010010101100 00010 01000100010111 01 0100100001 Impossible 001100010100100101 00111111000 000 01111001 001000000100010...
result:
ok 6110 lines