QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#477865 | #9118. Flip or Not | ucup-team1231# | WA | 1ms | 5688kb | C++14 | 2.1kb | 2024-07-14 11:56:34 | 2024-07-14 11:56:35 |
Judging History
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