| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 427979 | 2021-06-15T06:36:51 Z | juggernaut | Lamps (JOI19_lamps) | C++17 | 479 ms | 21872 KB |
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
typedef long long ll;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef IOI2021SG
#define printl(args...)printf(args)
#else
#define printl(args...)((void)0)
#endif
int n;
string a,b;
int dp[262144];
int go(int mask){
if(~dp[mask])return dp[mask];
dp[mask]=1e9;
for(int i=0;i<n;i++){
int A=mask;
int B=mask;
int C=mask;
for(int j=i;j<n;j++){
if(mask>>j&1)A^=(1<<j);
else B^=(1<<j);
C^=(1<<j);
umin(dp[mask],go(A)+1);
umin(dp[mask],go(B)+1);
umin(dp[mask],go(C)+1);
}
}
return dp[mask];
}
int main(){
memset(dp,-1,sizeof dp);
cin>>n>>b>>a;
int cnt=0;
int dest=0;
for(int i=0;i<n;i++)cnt|=((a[i]=='1')<<i);
for(int i=0;i<n;i++)dest|=((b[i]=='1')<<i);
dp[cnt]=0;
cout<<go(dest);
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 1228 KB | Output is correct |
| 2 | Correct | 1 ms | 1228 KB | Output is correct |
| 3 | Correct | 1 ms | 1228 KB | Output is correct |
| 4 | Correct | 1 ms | 1228 KB | Output is correct |
| 5 | Correct | 1 ms | 1228 KB | Output is correct |
| 6 | Correct | 1 ms | 1228 KB | Output is correct |
| 7 | Correct | 1 ms | 1228 KB | Output is correct |
| 8 | Correct | 473 ms | 21812 KB | Output is correct |
| 9 | Correct | 455 ms | 21812 KB | Output is correct |
| 10 | Correct | 200 ms | 11552 KB | Output is correct |
| 11 | Correct | 204 ms | 11552 KB | Output is correct |
| 12 | Correct | 471 ms | 21808 KB | Output is correct |
| 13 | Correct | 204 ms | 11588 KB | Output is correct |
| 14 | Correct | 471 ms | 21828 KB | Output is correct |
| 15 | Correct | 227 ms | 11556 KB | Output is correct |
| 16 | Correct | 442 ms | 21812 KB | Output is correct |
| 17 | Correct | 202 ms | 11556 KB | Output is correct |
| 18 | Correct | 451 ms | 21812 KB | Output is correct |
| 19 | Correct | 234 ms | 11468 KB | Output is correct |
| 20 | Correct | 443 ms | 21820 KB | Output is correct |
| 21 | Correct | 207 ms | 11556 KB | Output is correct |
| 22 | Correct | 447 ms | 21828 KB | Output is correct |
| 23 | Correct | 201 ms | 11556 KB | Output is correct |
| 24 | Correct | 443 ms | 21816 KB | Output is correct |
| 25 | Correct | 206 ms | 11560 KB | Output is correct |
| 26 | Correct | 451 ms | 21872 KB | Output is correct |
| 27 | Correct | 207 ms | 11552 KB | Output is correct |
| 28 | Correct | 89 ms | 6420 KB | Output is correct |
| 29 | Correct | 479 ms | 21836 KB | Output is correct |
| 30 | Correct | 212 ms | 11556 KB | Output is correct |
| 31 | Correct | 97 ms | 6420 KB | Output is correct |
| 32 | Correct | 436 ms | 21836 KB | Output is correct |
| 33 | Correct | 200 ms | 11568 KB | Output is correct |
| 34 | Correct | 90 ms | 6348 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 1228 KB | Output is correct |
| 2 | Correct | 1 ms | 1228 KB | Output is correct |
| 3 | Correct | 1 ms | 1228 KB | Output is correct |
| 4 | Correct | 1 ms | 1228 KB | Output is correct |
| 5 | Correct | 1 ms | 1228 KB | Output is correct |
| 6 | Correct | 1 ms | 1228 KB | Output is correct |
| 7 | Correct | 1 ms | 1228 KB | Output is correct |
| 8 | Correct | 473 ms | 21812 KB | Output is correct |
| 9 | Correct | 455 ms | 21812 KB | Output is correct |
| 10 | Correct | 200 ms | 11552 KB | Output is correct |
| 11 | Correct | 204 ms | 11552 KB | Output is correct |
| 12 | Correct | 471 ms | 21808 KB | Output is correct |
| 13 | Correct | 204 ms | 11588 KB | Output is correct |
| 14 | Correct | 471 ms | 21828 KB | Output is correct |
| 15 | Correct | 227 ms | 11556 KB | Output is correct |
| 16 | Correct | 442 ms | 21812 KB | Output is correct |
| 17 | Correct | 202 ms | 11556 KB | Output is correct |
| 18 | Correct | 451 ms | 21812 KB | Output is correct |
| 19 | Correct | 234 ms | 11468 KB | Output is correct |
| 20 | Correct | 443 ms | 21820 KB | Output is correct |
| 21 | Correct | 207 ms | 11556 KB | Output is correct |
| 22 | Correct | 447 ms | 21828 KB | Output is correct |
| 23 | Correct | 201 ms | 11556 KB | Output is correct |
| 24 | Correct | 443 ms | 21816 KB | Output is correct |
| 25 | Correct | 206 ms | 11560 KB | Output is correct |
| 26 | Correct | 451 ms | 21872 KB | Output is correct |
| 27 | Correct | 207 ms | 11552 KB | Output is correct |
| 28 | Correct | 89 ms | 6420 KB | Output is correct |
| 29 | Correct | 479 ms | 21836 KB | Output is correct |
| 30 | Correct | 212 ms | 11556 KB | Output is correct |
| 31 | Correct | 97 ms | 6420 KB | Output is correct |
| 32 | Correct | 436 ms | 21836 KB | Output is correct |
| 33 | Correct | 200 ms | 11568 KB | Output is correct |
| 34 | Correct | 90 ms | 6348 KB | Output is correct |
| 35 | Runtime error | 3 ms | 2508 KB | Execution killed with signal 11 |
| 36 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 1344 KB | Output is correct |
| 2 | Correct | 1 ms | 1228 KB | Output is correct |
| 3 | Correct | 1 ms | 1228 KB | Output is correct |
| 4 | Correct | 1 ms | 1228 KB | Output is correct |
| 5 | Correct | 2 ms | 1228 KB | Output is correct |
| 6 | Correct | 1 ms | 1228 KB | Output is correct |
| 7 | Correct | 50 ms | 5060 KB | Output is correct |
| 8 | Runtime error | 52 ms | 6712 KB | Execution killed with signal 11 |
| 9 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 1228 KB | Output is correct |
| 2 | Correct | 1 ms | 1228 KB | Output is correct |
| 3 | Correct | 1 ms | 1228 KB | Output is correct |
| 4 | Correct | 1 ms | 1228 KB | Output is correct |
| 5 | Correct | 1 ms | 1228 KB | Output is correct |
| 6 | Correct | 1 ms | 1228 KB | Output is correct |
| 7 | Correct | 1 ms | 1228 KB | Output is correct |
| 8 | Correct | 473 ms | 21812 KB | Output is correct |
| 9 | Correct | 455 ms | 21812 KB | Output is correct |
| 10 | Correct | 200 ms | 11552 KB | Output is correct |
| 11 | Correct | 204 ms | 11552 KB | Output is correct |
| 12 | Correct | 471 ms | 21808 KB | Output is correct |
| 13 | Correct | 204 ms | 11588 KB | Output is correct |
| 14 | Correct | 471 ms | 21828 KB | Output is correct |
| 15 | Correct | 227 ms | 11556 KB | Output is correct |
| 16 | Correct | 442 ms | 21812 KB | Output is correct |
| 17 | Correct | 202 ms | 11556 KB | Output is correct |
| 18 | Correct | 451 ms | 21812 KB | Output is correct |
| 19 | Correct | 234 ms | 11468 KB | Output is correct |
| 20 | Correct | 443 ms | 21820 KB | Output is correct |
| 21 | Correct | 207 ms | 11556 KB | Output is correct |
| 22 | Correct | 447 ms | 21828 KB | Output is correct |
| 23 | Correct | 201 ms | 11556 KB | Output is correct |
| 24 | Correct | 443 ms | 21816 KB | Output is correct |
| 25 | Correct | 206 ms | 11560 KB | Output is correct |
| 26 | Correct | 451 ms | 21872 KB | Output is correct |
| 27 | Correct | 207 ms | 11552 KB | Output is correct |
| 28 | Correct | 89 ms | 6420 KB | Output is correct |
| 29 | Correct | 479 ms | 21836 KB | Output is correct |
| 30 | Correct | 212 ms | 11556 KB | Output is correct |
| 31 | Correct | 97 ms | 6420 KB | Output is correct |
| 32 | Correct | 436 ms | 21836 KB | Output is correct |
| 33 | Correct | 200 ms | 11568 KB | Output is correct |
| 34 | Correct | 90 ms | 6348 KB | Output is correct |
| 35 | Runtime error | 3 ms | 2508 KB | Execution killed with signal 11 |
| 36 | Halted | 0 ms | 0 KB | - |