# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
949522 |
2024-03-19T10:16:57 Z |
pcc |
Lamps (JOI19_lamps) |
C++17 |
|
246 ms |
12852 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
int N;
string s;
ll ans = 1e9;
int dist[1<<20];
queue<int> q;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
memset(dist,-1,sizeof(dist));
cin>>N;
cin>>s;
int a = 0,b = 0;
for(int i = 0;i<N;i++){
if(s[i] == '1')a |= 1<<i;
}
cin>>s;
for(int i = 0;i<N;i++){
if(s[i] == '1')b |= 1<<i;
}
dist[a] = 0;
q.push(a);
while(!q.empty()){
auto now = q.front();
q.pop();
for(int l = 0;l<N;l++){
int ta = now,tb = now,tc = now;
for(int r = l;r<N;r++){
ta |= 1<<r;
if(tb&(1<<r))tb ^= (1<<r);
tc ^= 1<<r;
if(dist[ta] == -1){
dist[ta] = dist[now]+1;
q.push(ta);
}
if(dist[tb] == -1){
dist[tb] = dist[now]+1;
q.push(tb);
}
if(dist[tc] == -1){
dist[tc] = dist[now]+1;
q.push(tc);
}
}
}
}
cout<<dist[b];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4560 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
1 ms |
4440 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
232 ms |
4952 KB |
Output is correct |
9 |
Correct |
234 ms |
4960 KB |
Output is correct |
10 |
Correct |
111 ms |
4756 KB |
Output is correct |
11 |
Correct |
105 ms |
4700 KB |
Output is correct |
12 |
Correct |
226 ms |
5032 KB |
Output is correct |
13 |
Correct |
108 ms |
4700 KB |
Output is correct |
14 |
Correct |
237 ms |
5216 KB |
Output is correct |
15 |
Correct |
104 ms |
4812 KB |
Output is correct |
16 |
Correct |
235 ms |
5068 KB |
Output is correct |
17 |
Correct |
106 ms |
4700 KB |
Output is correct |
18 |
Correct |
238 ms |
5036 KB |
Output is correct |
19 |
Correct |
99 ms |
4800 KB |
Output is correct |
20 |
Correct |
240 ms |
5060 KB |
Output is correct |
21 |
Correct |
107 ms |
4808 KB |
Output is correct |
22 |
Correct |
234 ms |
5080 KB |
Output is correct |
23 |
Correct |
114 ms |
4800 KB |
Output is correct |
24 |
Correct |
246 ms |
4812 KB |
Output is correct |
25 |
Correct |
109 ms |
5036 KB |
Output is correct |
26 |
Correct |
228 ms |
5088 KB |
Output is correct |
27 |
Correct |
100 ms |
4776 KB |
Output is correct |
28 |
Correct |
48 ms |
4700 KB |
Output is correct |
29 |
Correct |
246 ms |
5004 KB |
Output is correct |
30 |
Correct |
106 ms |
4796 KB |
Output is correct |
31 |
Correct |
47 ms |
4676 KB |
Output is correct |
32 |
Correct |
227 ms |
4796 KB |
Output is correct |
33 |
Correct |
102 ms |
4784 KB |
Output is correct |
34 |
Correct |
52 ms |
4684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4560 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
1 ms |
4440 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
232 ms |
4952 KB |
Output is correct |
9 |
Correct |
234 ms |
4960 KB |
Output is correct |
10 |
Correct |
111 ms |
4756 KB |
Output is correct |
11 |
Correct |
105 ms |
4700 KB |
Output is correct |
12 |
Correct |
226 ms |
5032 KB |
Output is correct |
13 |
Correct |
108 ms |
4700 KB |
Output is correct |
14 |
Correct |
237 ms |
5216 KB |
Output is correct |
15 |
Correct |
104 ms |
4812 KB |
Output is correct |
16 |
Correct |
235 ms |
5068 KB |
Output is correct |
17 |
Correct |
106 ms |
4700 KB |
Output is correct |
18 |
Correct |
238 ms |
5036 KB |
Output is correct |
19 |
Correct |
99 ms |
4800 KB |
Output is correct |
20 |
Correct |
240 ms |
5060 KB |
Output is correct |
21 |
Correct |
107 ms |
4808 KB |
Output is correct |
22 |
Correct |
234 ms |
5080 KB |
Output is correct |
23 |
Correct |
114 ms |
4800 KB |
Output is correct |
24 |
Correct |
246 ms |
4812 KB |
Output is correct |
25 |
Correct |
109 ms |
5036 KB |
Output is correct |
26 |
Correct |
228 ms |
5088 KB |
Output is correct |
27 |
Correct |
100 ms |
4776 KB |
Output is correct |
28 |
Correct |
48 ms |
4700 KB |
Output is correct |
29 |
Correct |
246 ms |
5004 KB |
Output is correct |
30 |
Correct |
106 ms |
4796 KB |
Output is correct |
31 |
Correct |
47 ms |
4676 KB |
Output is correct |
32 |
Correct |
227 ms |
4796 KB |
Output is correct |
33 |
Correct |
102 ms |
4784 KB |
Output is correct |
34 |
Correct |
52 ms |
4684 KB |
Output is correct |
35 |
Runtime error |
6 ms |
8924 KB |
Execution killed with signal 11 |
36 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
2 ms |
4556 KB |
Output is correct |
7 |
Runtime error |
10 ms |
12852 KB |
Execution killed with signal 11 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4560 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
1 ms |
4440 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
232 ms |
4952 KB |
Output is correct |
9 |
Correct |
234 ms |
4960 KB |
Output is correct |
10 |
Correct |
111 ms |
4756 KB |
Output is correct |
11 |
Correct |
105 ms |
4700 KB |
Output is correct |
12 |
Correct |
226 ms |
5032 KB |
Output is correct |
13 |
Correct |
108 ms |
4700 KB |
Output is correct |
14 |
Correct |
237 ms |
5216 KB |
Output is correct |
15 |
Correct |
104 ms |
4812 KB |
Output is correct |
16 |
Correct |
235 ms |
5068 KB |
Output is correct |
17 |
Correct |
106 ms |
4700 KB |
Output is correct |
18 |
Correct |
238 ms |
5036 KB |
Output is correct |
19 |
Correct |
99 ms |
4800 KB |
Output is correct |
20 |
Correct |
240 ms |
5060 KB |
Output is correct |
21 |
Correct |
107 ms |
4808 KB |
Output is correct |
22 |
Correct |
234 ms |
5080 KB |
Output is correct |
23 |
Correct |
114 ms |
4800 KB |
Output is correct |
24 |
Correct |
246 ms |
4812 KB |
Output is correct |
25 |
Correct |
109 ms |
5036 KB |
Output is correct |
26 |
Correct |
228 ms |
5088 KB |
Output is correct |
27 |
Correct |
100 ms |
4776 KB |
Output is correct |
28 |
Correct |
48 ms |
4700 KB |
Output is correct |
29 |
Correct |
246 ms |
5004 KB |
Output is correct |
30 |
Correct |
106 ms |
4796 KB |
Output is correct |
31 |
Correct |
47 ms |
4676 KB |
Output is correct |
32 |
Correct |
227 ms |
4796 KB |
Output is correct |
33 |
Correct |
102 ms |
4784 KB |
Output is correct |
34 |
Correct |
52 ms |
4684 KB |
Output is correct |
35 |
Runtime error |
6 ms |
8924 KB |
Execution killed with signal 11 |
36 |
Halted |
0 ms |
0 KB |
- |