# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
854971 |
2023-09-29T14:18:23 Z |
Tenis0206 |
W (RMI18_w) |
C++11 |
|
600 ms |
3932 KB |
#include <bits/stdc++.h>
using namespace std;
const int nmax = 3e5;
const int Mod = 1e9 + 7;
int n;
int v[nmax + 5];
pair<int,int> c[nmax + 5];
int dp[(1<<5) + 5], aux[(1<<5) + 5];
int lgput(int a, int b)
{
int p = 1;
while(b)
{
if(b%2==0)
{
b/=2;
a = 1LL * a * a % Mod;
}
else
{
--b;
p = 1LL * p * a % Mod;
}
}
return p;
}
int invmod(int x)
{
return lgput(x,Mod-2);
}
int comb(int n, int k)
{
int rez = 1;
for(int i=1;i<=n-k;i++)
{
rez = 1LL * rez * i % Mod;
}
for(int i=1;i<=n-k;i++)
{
rez = 1LL * rez * invmod(i) % Mod;
}
return rez;
}
bool valid(int mask)
{
if((mask & 1) != 0 && (mask & 2) == 0)
{
return false;
}
if((mask & 4) != 0 && (mask & 2) == 0)
{
return false;
}
if((mask & 4) != 0 && (mask & 8) == 0)
{
return false;
}
if((mask & 16) != 0 && (mask & 8) == 0)
{
return false;
}
return true;
}
bool valid_last(int last_mask, int mask)
{
if((last_mask & 1) == 0 && (mask & 1) != 0 && (last_mask & 2) == 0 && (mask & 2) != 0)
{
return false;
}
if((last_mask & 2) == 0 && (mask & 2) != 0 && (last_mask & 4) == 0 && (mask & 4) != 0)
{
return false;
}
if((last_mask & 4) == 0 && (mask & 4) != 0 && (last_mask & 8) == 0 && (mask & 8) != 0)
{
return false;
}
if((last_mask & 8) == 0 && (mask & 8) != 0 && (last_mask & 16) == 0 && (mask & 16) != 0)
{
return false;
}
return true;
}
int get_opt(int last_mask, int mask)
{
int nr = 0;
if((mask & 2) != 0 && (last_mask & 1) == 0 && !((last_mask & 1) == 0 && (mask & 1) != 0) && !((last_mask & 2) == 0 && (mask & 2) != 0))
{
++nr;
}
if((mask & 2) != 0 && (last_mask & 4) == 0 && !((last_mask & 2) == 0 && (mask & 2) != 0) && !((last_mask & 4) == 0 && (mask & 4) != 0))
{
++nr;
}
if((mask & 8) != 0 && (last_mask & 4) == 0 && !((last_mask & 4) == 0 && (mask & 4) != 0) && !((last_mask & 8) == 0 && (mask & 8) != 0))
{
++nr;
}
if((mask & 8) != 0 && (last_mask & 16) == 0 && !((last_mask & 8) == 0 && (mask & 8) != 0) && !((last_mask & 16) == 0 && (mask & 16) != 0))
{
++nr;
}
if((last_mask & 1) == 0 && (mask & 1) != 0)
{
++nr;
}
if((last_mask & 2) == 0 && (mask & 2) != 0)
{
++nr;
}
if((last_mask & 4) == 0 && (mask & 4) != 0)
{
++nr;
}
if((last_mask & 8) == 0 && (mask & 8) != 0)
{
++nr;
}
if((last_mask & 16) == 0 && (mask & 16) != 0)
{
++nr;
}
return nr;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef home
freopen("nr.in","r",stdin);
freopen("nr.out","w",stdout);
#endif // home
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>v[i];
}
sort(v+1,v+n+1);
int nr = 0;
for(int i=1; i<=n; i++)
{
if(v[i]!=v[i-1])
{
c[++nr].first = v[i];
}
++c[nr].second;
}
dp[0] = 1;
for(int i=1; i<=nr; i++)
{
for(int mask=0; mask<(1<<5); mask++)
{
if(!valid(mask))
{
continue;
}
for(int last_mask=0; last_mask<(1<<5); last_mask++)
{
if((mask & last_mask) != last_mask)
{
continue;
}
if(!valid_last(last_mask, mask))
{
continue;
}
int nr_free = c[i].second - (__builtin_popcount(mask) - __builtin_popcount(last_mask));
if(nr_free < 0)
{
continue;
}
int nropt = get_opt(last_mask, mask);
aux[mask] += 1LL * comb(nr_free + nropt - 1, nropt - 1) * dp[last_mask] % Mod;
aux[mask] %= Mod;
}
}
for(int mask=0;mask<(1<<5);mask++)
{
dp[mask] = aux[mask];
aux[mask] = 0;
}
}
cout<<dp[(1<<5) - 1]<<'\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
3 |
Incorrect |
507 ms |
640 KB |
Output isn't correct |
4 |
Execution timed out |
1058 ms |
1628 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Incorrect |
4 ms |
348 KB |
Output isn't correct |
3 |
Incorrect |
105 ms |
2788 KB |
Output isn't correct |
4 |
Incorrect |
359 ms |
3060 KB |
Output isn't correct |
5 |
Execution timed out |
709 ms |
3448 KB |
Time limit exceeded |
6 |
Execution timed out |
1054 ms |
3932 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
4 |
Incorrect |
3 ms |
344 KB |
Output isn't correct |
5 |
Incorrect |
21 ms |
480 KB |
Output isn't correct |
6 |
Incorrect |
20 ms |
348 KB |
Output isn't correct |
7 |
Incorrect |
60 ms |
524 KB |
Output isn't correct |
8 |
Execution timed out |
1014 ms |
836 KB |
Time limit exceeded |
9 |
Execution timed out |
1035 ms |
1112 KB |
Time limit exceeded |
10 |
Execution timed out |
1043 ms |
3672 KB |
Time limit exceeded |