QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#82607 | #69. Lamps | lmeowdn | 4 | 138ms | 83832kb | C++14 | 1.6kb | 2023-02-28 13:50:14 | 2023-02-28 13:50:19 |
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][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]=0;
int ans=0x3f3f3f3f;
rep(i,1,n) rep(j,0,1) rep(k,0,2) rep(l,0,2) {
bool flag=1;
if(l==0) {
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);
}
} else if(l==1) {
flag=(b[i]==0);
} else {
flag=(b[i]==1);
}
if(!flag) continue;
rep(j0,0,1) rep(k0,0,2) rep(l0,0,2) {
int w=(j0==0&&j==1)+(k!=0&&k0!=k)+(l!=0&&l0!=l);
f[i][j][k][l]=min(f[i][j][k][l],f[i-1][j0][k0][l0]+w);
}
if(i==n) ans=min(ans,f[i][j][k][l]);
}
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: 12ms
memory: 79784kb
input:
1 1 0
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 4ms
memory: 78336kb
input:
1 1 1
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 22ms
memory: 78584kb
input:
2 10 01
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 17ms
memory: 78312kb
input:
2 01 10
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 4ms
memory: 78376kb
input:
2 11 00
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 8ms
memory: 79972kb
input:
2 11 10
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 1ms
memory: 79120kb
input:
2 11 01
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 3ms
memory: 78012kb
input:
18 000000000000000000 101010101010101010
output:
9
result:
ok single line: '9'
Test #9:
score: 0
Accepted
time: 8ms
memory: 78848kb
input:
18 111111111111111111 010101010101010101
output:
9
result:
ok single line: '9'
Test #10:
score: 0
Accepted
time: 7ms
memory: 79736kb
input:
17 11111111111111111 10101010101010101
output:
8
result:
ok single line: '8'
Test #11:
score: 0
Accepted
time: 15ms
memory: 78724kb
input:
17 00000000000000000 01010101010101010
output:
8
result:
ok single line: '8'
Test #12:
score: 0
Accepted
time: 11ms
memory: 78512kb
input:
18 110111100010101111 010111100011100000
output:
3
result:
ok single line: '3'
Test #13:
score: 0
Accepted
time: 11ms
memory: 78688kb
input:
17 10110110110110101 01011100100110000
output:
4
result:
ok single line: '4'
Test #14:
score: 0
Accepted
time: 13ms
memory: 78592kb
input:
18 000000110001001000 111111001011011100
output:
3
result:
ok single line: '3'
Test #15:
score: 0
Accepted
time: 13ms
memory: 79688kb
input:
17 11011010101011111 10011000100000101
output:
4
result:
ok single line: '4'
Test #16:
score: 0
Accepted
time: 23ms
memory: 79088kb
input:
18 011011101011011000 001010011011110001
output:
4
result:
ok single line: '4'
Test #17:
score: 0
Accepted
time: 8ms
memory: 79304kb
input:
17 10111101010001010 00111001111010010
output:
4
result:
ok single line: '4'
Test #18:
score: 0
Accepted
time: 3ms
memory: 78260kb
input:
18 100110111111001010 100000001101000010
output:
3
result:
ok single line: '3'
Test #19:
score: 0
Accepted
time: 3ms
memory: 78552kb
input:
17 00101111101000011 00111001111110001
output:
3
result:
ok single line: '3'
Test #20:
score: 0
Accepted
time: 8ms
memory: 79032kb
input:
18 001010100000100100 000100110011100110
output:
4
result:
ok single line: '4'
Test #21:
score: 0
Accepted
time: 15ms
memory: 77548kb
input:
17 11101100011001011 11101110111111111
output:
2
result:
ok single line: '2'
Test #22:
score: 0
Accepted
time: 8ms
memory: 78308kb
input:
18 010101110011000110 011001110000001110
output:
3
result:
ok single line: '3'
Test #23:
score: 0
Accepted
time: 11ms
memory: 78828kb
input:
17 10010100000010010 10010111101001000
output:
4
result:
ok single line: '4'
Test #24:
score: 0
Accepted
time: 11ms
memory: 79708kb
input:
18 001111100001101100 001111001111111100
output:
2
result:
ok single line: '2'
Test #25:
score: 0
Accepted
time: 3ms
memory: 79924kb
input:
17 10011011100011110 10000000011100010
output:
2
result:
ok single line: '2'
Test #26:
score: -6
Wrong Answer
time: 7ms
memory: 79180kb
input:
18 010100101101110100 111000010010101001
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: 17ms
memory: 77964kb
input:
1 0 0
output:
0
result:
ok single line: '0'
Test #60:
score: 0
Accepted
time: 3ms
memory: 79884kb
input:
1 0 1
output:
1
result:
ok single line: '1'
Test #61:
score: 0
Accepted
time: 11ms
memory: 78148kb
input:
2 00 00
output:
0
result:
ok single line: '0'
Test #62:
score: 0
Accepted
time: 1ms
memory: 78832kb
input:
2 00 10
output:
1
result:
ok single line: '1'
Test #63:
score: 0
Accepted
time: 3ms
memory: 77436kb
input:
2 00 01
output:
1
result:
ok single line: '1'
Test #64:
score: 0
Accepted
time: 7ms
memory: 78596kb
input:
2 00 11
output:
1
result:
ok single line: '1'
Test #65:
score: 0
Accepted
time: 128ms
memory: 83564kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0
result:
ok single line: '0'
Test #66:
score: 0
Accepted
time: 137ms
memory: 83648kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
500000
result:
ok single line: '500000'
Test #67:
score: 0
Accepted
time: 131ms
memory: 83612kb
input:
999999 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
500000
result:
ok single line: '500000'
Test #68:
score: 0
Accepted
time: 129ms
memory: 83620kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
500000
result:
ok single line: '500000'
Test #69:
score: 0
Accepted
time: 118ms
memory: 83620kb
input:
999999 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
499999
result:
ok single line: '499999'
Test #70:
score: 0
Accepted
time: 113ms
memory: 83800kb
input:
999999 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
1
result:
ok single line: '1'
Test #71:
score: 0
Accepted
time: 138ms
memory: 83828kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
100
result:
ok single line: '100'
Test #72:
score: 0
Accepted
time: 130ms
memory: 83832kb
input:
999999 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12345
result:
ok single line: '12345'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%