QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#76566	#4256. 最大异或和	lmeowdn	0	209ms	4520kb	C++14	2.2kb	2023-02-10 20:17:18	2023-02-10 20:17:19

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-02-10 20:17:19]
评测

测评结果：0
用时：209ms
内存：4520kb

查看

[2023-02-10 20:17:18]
提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;

int read() {
    int x=0,w=1; char c=getchar(); 
    while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
    while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}
    return x*w;
}

const int N=2009;
typedef bitset<N> bset;
int n,m,q,s[N],t[N],tot,id[N];
bset a[N],b[N],p[N];

void bread(bset &res) {
    static char c[1009]; scanf("%s",c);
    rep(i,0,m-1) if(c[i]=='1') res.set(m-1-i);
}
void elim(int k) {
    per(i,m-1,0) if(b[k][i]) {
        if(s[i]) b[k]^=b[s[i]], p[s[i]]^=p[k];
        else {s[i]=k, t[k]=i; break;}
    }
}
void mdf(int i,bset w) {
    //cout<<"MDF "<<i<<endl;
    //per(i,m-1,0) cout<<w[i]; puts("");
    int j=0; tot=0;
    rep(k,1,n) if(p[k][i]) {
        if(b[k].none()) {j=k; break;}
        else if((!j)||t[k]<t[j]) j=k;
        id[++tot]=k;
    }
    if(b[j].any()) {
        rep(k,1,tot) if(id[k]!=j) b[id[k]]^=b[j], p[j]^=p[id[k]];
    }
    //cout<<j<<endl;
    b[j]^=w; if(t[j]) s[t[j]]=0;  t[j]=-1; elim(j);
    //rep(i,1,n) {
    //    per(j,m-1,0) putchar('0'+b[i][j]); puts("");
    //}
    //rep(i,0,m-1) cout<<i<<" "<<s[i]<<endl;
}
bset qry() {
    bset res;
    per(i,m-1,0) if(!res[i]&&s[i]) res^=b[s[i]];
    return res;
}

signed main() {
    n=read(), m=read(), q=read();
    rep(i,1,n) bread(a[i]), b[i]=b[i-1]^a[i], p[i].set(i), t[i]=-1;
    rep(i,1,n) elim(i);
    rep(i,1,q) {
        int op=read(),x,y; bset w;
        if(op==1) {
            x=read(), y=read(); bread(w);
            mdf(x,w); if(y!=n) mdf(y+1,w);
        } else if(op==2) {
            x=read(), y=read(); bread(w);
            mdf(x,w^a[x]); if(y!=n) mdf(y+1,w^a[y]); a[x]=w;
            rep(i,x+1,y) if(a[i]!=a[i-1]) mdf(i,a[i]^a[i-1]);
            rep(i,x+1,y) a[i]=w;
        } else {
            bset ans=qry();
            per(i,m-1,0) putchar('0'+ans[i]);
            putchar('\n');
        }
    }
    return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 0

Wrong Answer

time: 3ms

memory: 3616kb

input:

10 10 1000
0000001100
0110100010
0000110101
0100011011
0111111000
0111100110
0111100001
1000111111
0001100011
1110111101
1 3 6 1011011010
3
2 4 8 1110001101
3
2 4 5 0110010111
3
2 5 5 0111111110
3
2 4 7 0101000101
3
2 2 2 1011001111
3
2 1 1 0100101010
3
2 6 7 0001000101
3
2 1 9 0000100100
3
2 7 10 0...

output:

result:

wrong answer 2nd words differ - expected: '1111101110', found: '1111011111'

Test #2:

score: 0

Wrong Answer

time: 11ms

memory: 3840kb

input:

500 500 10
1100000100011111011100000111000001010110011001100101010011111101100110111001110111011110000001011100001000011101011110010111001100111011010100110110110011101101001100110110000011000111110011100111100011000010100000000000111011101010111001001001111000111110111011110110001010110010010111010...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

wrong answer 1st words differ - expected: '111111111111111111111111111111...1101110010110111111111001100011', found: '111111111111111111111111111111...1101010110100011101001000001100'

Test #3:

score: 0

Wrong Answer

time: 2ms

memory: 3684kb

input:

120 120 120
000000100110110101001001111111000101001111000111010101001100100000111000110110110100110010101000101011000110100011001110
001100001110110100010111101110111010010010011001010011001110011001100011111011011111010111111101011011010011110110011001
0001010011110011101011110010101100001001011001...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010000000
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111110111
1111111111111111111111111111111111111111111111111111111111...

result:

wrong answer 1st words differ - expected: '111111111111111111111111111111...1111111111111111111110110011110', found: '111111111111111111111111111111...1111111111111111111111010000000'

Test #4:

score: 0

Runtime Error

input:

2000 2000 10
01000011000011101010010110100010000011111000011010100110110111011010001111010000110011010001111100000011101100010111010001100110100110101110100111000011000011100011111011010111100010001101100110100100000011000100111111000100110000000001100111001001110111010011101111110101100010011001100...

output:

result:

Test #5:

score: 0

Runtime Error

input:

1800 1800 1800
001101010111111011100100010111011100010011011000111111101101001010101110110001110001001010101101101001011111000110111010001110010000110110110100011110001010111111111100100100010010011010010110010001010011110010110010101010110001101100110101110101011000100100011010001101100010101011001...

output:

result:

Test #6:

score: 0

Runtime Error

input:

1800 1800 1800
000101001100000110010101010100101110110011100011101100100000101100010011100010101101011001111110000100001111001101111011010110001101111000101101000110000010001001110011000000001011010010011010011111011000110111100101111010011000001100111001010010011001110010110000000001110001000100000...

output:

result:

Test #7:

score: 0

Runtime Error

input:

1800 1800 1800
101110010111110011100100001001110110110001111110101001000001001001101001110111010000100100001001000001110100101010010101001000001101101011101001101111111000101000000011111110011001001011110101101110001010111111001110011010110000010010000101100000000000101100001011100000010100000110111...

output:

result:

Test #8:

score: 0

Wrong Answer

time: 209ms

memory: 4520kb

input:

1500 1500 1500
101000101000111101000010000100111110001110011101101001101101000001101111111111101010011100010011011000101010001110101111010100100111100001100101001100010100101001101001011011100001000111001000111111100010111011100010101101100101111100100110010110010001111100001110101011011011110010111...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

wrong answer 1st words differ - expected: '111111111111111111111111111111...0111101101000110000110110000000', found: '111111111111111111111111111111...1111111111111111111111111111011'

Test #9:

score: 0

Runtime Error

input:

1800 1800 1800
010010010101101101010000111001111010110101011000101000011101000111110111010100010101100011101101001001111111000010101111001100100000110001000101111000001101001100010000010110001110011100100001110101110101000101110011101100001110010000010011000010011101010100111110101101100001110101101...

output:

result:

Test #10:

score: 0

Runtime Error

input:

2000 2000 2000
010101100001100000010011101110000011000010000011110011110010010100010100110111110111010101010110010010000011111011010101000111000011101100110111000101011111110100010110100001001110110001100111010100001101000110010010001111100010111010110001100010101111001111100100101111011011011110100...