QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#82605 | #69. Lamps | lmeowdn | 4 | 30ms | 36812kb | C++14 | 1.4kb | 2023-02-28 13:47:50 | 2023-02-28 13:47:54 |
Judging History
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
#define popc __builtin_popcount
#define sgn(x) ((x)&1?-1:1)
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=1e6+9;
int n,f[N][2][3],a[N],b[N];
char s[N],t[N];
signed main() {
n=read();
scanf("%s%s",s+1,t+1);
rep(i,1,n) a[i]=(s[i]=='1');
rep(i,1,n) b[i]=(t[i]=='1');
memset(f,0x3f,sizeof(f));
f[0][0][0]=0;
int ans=0x3f3f3f3f;
rep(i,1,n) rep(j,0,1) rep(k,0,2) {
bool flag=1;
if(k==0) {
if(j==0) flag=(a[i]==b[i]);
else flag=(a[i]!=b[i]);
} else if(k==1) {
flag=(b[i]==0);
} else {
flag=(b[i]==1);
}
if(!flag) continue;
rep(j0,0,1) rep(k0,0,2) {
int w=(j0==0&&j==1)+(k!=0&&k0!=k);
f[i][j][k]=min(f[i][j][k],f[i-1][j0][k0]+w);
}
if(i==n) ans=min(ans,f[i][j][k]);
}
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 4ms
memory: 32200kb
input:
1 1 0
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 5ms
memory: 31640kb
input:
1 1 1
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 4ms
memory: 31428kb
input:
2 10 01
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 4ms
memory: 31292kb
input:
2 01 10
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 2ms
memory: 32780kb
input:
2 11 00
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 2ms
memory: 31752kb
input:
2 11 10
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 31096kb
input:
2 11 01
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 7ms
memory: 32812kb
input:
18 000000000000000000 101010101010101010
output:
9
result:
ok single line: '9'
Test #9:
score: 0
Accepted
time: 7ms
memory: 32036kb
input:
18 111111111111111111 010101010101010101
output:
9
result:
ok single line: '9'
Test #10:
score: 0
Accepted
time: 4ms
memory: 31804kb
input:
17 11111111111111111 10101010101010101
output:
8
result:
ok single line: '8'
Test #11:
score: 0
Accepted
time: 0ms
memory: 33060kb
input:
17 00000000000000000 01010101010101010
output:
8
result:
ok single line: '8'
Test #12:
score: 0
Accepted
time: 0ms
memory: 30576kb
input:
18 110111100010101111 010111100011100000
output:
3
result:
ok single line: '3'
Test #13:
score: 0
Accepted
time: 1ms
memory: 32460kb
input:
17 10110110110110101 01011100100110000
output:
4
result:
ok single line: '4'
Test #14:
score: 0
Accepted
time: 3ms
memory: 31104kb
input:
18 000000110001001000 111111001011011100
output:
3
result:
ok single line: '3'
Test #15:
score: 0
Accepted
time: 4ms
memory: 30760kb
input:
17 11011010101011111 10011000100000101
output:
4
result:
ok single line: '4'
Test #16:
score: -6
Wrong Answer
time: 0ms
memory: 32484kb
input:
18 011011101011011000 001010011011110001
output:
5
result:
wrong answer 1st lines differ - expected: '4', found: '5'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 4
Accepted
Test #59:
score: 4
Accepted
time: 4ms
memory: 31996kb
input:
1 0 0
output:
0
result:
ok single line: '0'
Test #60:
score: 0
Accepted
time: 1ms
memory: 31256kb
input:
1 0 1
output:
1
result:
ok single line: '1'
Test #61:
score: 0
Accepted
time: 0ms
memory: 32852kb
input:
2 00 00
output:
0
result:
ok single line: '0'
Test #62:
score: 0
Accepted
time: 4ms
memory: 32632kb
input:
2 00 10
output:
1
result:
ok single line: '1'
Test #63:
score: 0
Accepted
time: 3ms
memory: 31900kb
input:
2 00 01
output:
1
result:
ok single line: '1'
Test #64:
score: 0
Accepted
time: 1ms
memory: 33040kb
input:
2 00 11
output:
1
result:
ok single line: '1'
Test #65:
score: 0
Accepted
time: 18ms
memory: 36776kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0
result:
ok single line: '0'
Test #66:
score: 0
Accepted
time: 23ms
memory: 36812kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
500000
result:
ok single line: '500000'
Test #67:
score: 0
Accepted
time: 7ms
memory: 36676kb
input:
999999 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
500000
result:
ok single line: '500000'
Test #68:
score: 0
Accepted
time: 11ms
memory: 36808kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
500000
result:
ok single line: '500000'
Test #69:
score: 0
Accepted
time: 18ms
memory: 36736kb
input:
999999 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
499999
result:
ok single line: '499999'
Test #70:
score: 0
Accepted
time: 30ms
memory: 36776kb
input:
999999 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
1
result:
ok single line: '1'
Test #71:
score: 0
Accepted
time: 20ms
memory: 36804kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
100
result:
ok single line: '100'
Test #72:
score: 0
Accepted
time: 11ms
memory: 36776kb
input:
999999 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12345
result:
ok single line: '12345'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%