QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#477865#9118. Flip or Notucup-team1231#WA 1ms5688kbC++142.1kb2024-07-14 11:56:342024-07-14 11:56:35

Judging History

你现在查看的是最新测评结果

  • [2024-07-14 11:56:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5688kb
  • [2024-07-14 11:56:34]
  • 提交

answer

#pragma GCC optimize("Ofast","-funroll-all-loops")
#include <bits/stdc++.h>
using namespace std;
int n;
typedef bitset<5005> bb;
char s[5005],t[5005];
vector<int> A,B;
#define pb push_back
bb mask_all;
void inp(vector<int>&s) {
    int m,x; cin>>m;
    while(m--)
        cin>>x,s.pb(x-1);
}
bb lsh(bb a,int u) {
    u%=n; if(u<0) u+=n;
    return ((a<<u) | (a>>(n-u))) & mask_all;
}
bb rsh(bb a,int u) {
    return lsh(a,-u);
}
#define S 10005
bb out[S],tg[S];
bb bs[5005],bx[5005];
void ins(bb a,int bi) {
    bb b; b.reset(); b[bi]=1;
    for(int i=n-1;i>=0;--i) {
        if(a[i]) {
            a^=bs[i],b^=bx[i];
            if(a[i]) {
                bs[i]=a, bx[i]=b;
                for(int j=n-1;j>i;--j) if(bs[j][i]) {
                    bs[j]^=bs[i],bx[j]^=bx[i];
                }
                return;
            }
        }
    }
}
int main() {
    cin>>n>>s>>t;
    for(int i=0;i<n;++i) mask_all[i]=1;
    inp(A); inp(B);
    bb nd; nd.reset();
    for(int i=0;i<n;++i) if(t[i]=='1') nd[i]=1;
    for(int i=0;i<S;++i) {
        out[i][0]=1;
        for(int j:A) {
            if(i>=n-j)
                out[i]^=lsh(out[i-(n-j)],j);
            else
                out[i][j]=!out[i][j];
        }
        for(int j:B) {
            if(i>=n-j)
                tg[i]^=lsh(out[i-(n-j)],j-i);
            else
                tg[i][(j-i+n)%n]=!tg[i][(j-i+n)%n];
        }
        ins(tg[i],i);
        bb oo=nd;
        for(int a=0;a<n;++a)
            if(s[a]=='1') {
                int op=i-(n-a-1);
                if(op>=0) oo^=rsh(out[op],-op);
                else op=(op%n+n)%n, oo[op]=!oo[op];
            }
        bb bx; bx.reset();
        bool bad=0;
        for(int i=n-1;i>=0;--i) if(oo[i]) {
            oo^=bs[i],bx^=::bx[i];
            if(oo[i]) {
                bad=1; break;
            }
        }
        if(!bad) {
            cout<<i+1<<endl;
            for(int j=i;j>=0;--j)
                cout<<bx[j];
            cout<<endl;
            exit(0);
        }
    }
    cout<<-1<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5688kb

input:

5
00001
00111
3
1 2 3
2
3 5

output:

4
0110

result:

wrong answer f_s != f_t