#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef int64_t ll;
#define int ll
const int N = 100;
const int mod = 1e9 + 7;
int a[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
set<int> ss;
function<void(int)> add = [&](int x){
if(ss.count(x)){
ss.erase(x);
add(x + 1);
if(x > 2) add(x - 2);
else if(x == 2) add(x - 1);
return;
}
if(ss.count(x + 1)){
ss.erase(x + 1);
add(x + 2);
return;
}
if(ss.count(x - 1)){
ss.erase(x - 1);
add(x + 1);
return;
}
ss.insert(x);
};
for(int i=0;i<n;i++){
add(a[i]);
vector<int> f;
for(auto x : ss) f.push_back(x);
//~ for(auto x : f) cout<<x<<" ";
//~ cout<<"\n";
ar<int, 2> dp {};
dp[0] = 1;
int m = f.size(), last = 0;
for(int i=0,j=0;i<m;){
ar<int, 2> tp {};
while(j<m && (j == i || f[j] == f[j-1] + 2)) j++;
int p = f[i] - last - 1;
tp[0] = dp[0] * 1ll * (1 + (p / 2) * 1ll * (j - i - 1) % mod) % mod;
tp[0] = (tp[0] + dp[1] * 1ll * (1 + ((p + 1) / 2) * 1ll * (j - i - 1) % mod)) % mod;
tp[1] = dp[0] * 1ll * (p / 2) % mod;
tp[1] = (tp[1] + dp[1] * 1ll * ((p + 1) / 2)) % mod;
swap(tp, dp);
//~ cout<<dp[0]<<" "<<dp[1]<<"\n";
last = f[j - 1];
i = j;
}
//~ cout<<dp[0]<<" "<<dp[1]<<"\n";
cout<<(dp[0] + dp[1]) % mod<<"\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
272 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
272 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
324 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
272 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
324 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
324 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
324 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
324 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
320 KB |
Output is correct |
23 |
Correct |
1 ms |
320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
272 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
324 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
324 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
324 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
324 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
320 KB |
Output is correct |
23 |
Correct |
1 ms |
320 KB |
Output is correct |
24 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
25 |
Halted |
0 ms |
0 KB |
- |