#include<bits/stdc++.h>
#define eb emplace_back
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {\
for(auto pv : a) b << pv << " ";\
b << "\n";\
}
using namespace std;
typedef long long ll;
ll MOD = 1000000007;
ll inv(ll a){
ll b = MOD - 2;
ll ans = 1;
while(b > 0){
if(b & 1) ans = ans * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return ans;
}
ll solve(vector<int> a){
lsort(a);
vector<int> cnt(501);
for(int i : a) cnt[i]++;
cnt[2] += cnt[1] / 2;
cnt[1] %= 2;
for(int j = 1; j <= 500; j++){
for(int i = 498; i >= 1; i--){
int t = min(cnt[i], cnt[i + 1]);
cnt[i] -= t;
cnt[i + 1] -= t;
cnt[i + 2] += t;
}
for(int i = 500; i - 2 >= 1; i--){
if(cnt[i] > 2) return 0;
if(cnt[i] <= 1) continue;
cnt[i - 1]++;
cnt[i - 2]++;
cnt[i] = 1;
}
}
if(cnt[1] > 1 || cnt[2] > 1) return 0;
//for(int i = 1; i <= 20; i++) cerr << cnt[i] << " ";
//cerr << "\n";
vector<int> dp(501);
dp[0] = 1;
for(int i = 499; i >= 0; i--){
for(int j = i + 1; j <= 500; j++){
if(i % 2 != j % 2){
if(cnt[i + 1] == 0 || j == i + 1) dp[0] += dp[j];
dp[0] %= MOD;
if(cnt[i] == 1) dp[j] = 0;
}
}
if(cnt[i] == 1){
dp[i] = dp[0];
dp[0] = 0;
}
//if(i > 20) continue;
//cerr << "dp " << i << " ";
//for(int j = 0; j <= 20; j++) cerr << dp[j] << " ";
//cerr << "\n";
}
return dp[0];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
assert(n <= 100);
vector<int> a;
for(int i = 0; i < n; i++){
int x;
cin >> x;
assert(x <= 100);
a.eb(x);
cout << solve(a) << "\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |