| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 854969 |
2023-09-29T14:09:44 Z |
Tenis0206 |
W (RMI18_w) |
C++11 |
|
600 ms |
6228 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)
{
++nr;
}
if((mask & 2) != 0 && (last_mask & 4) == 0)
{
++nr;
}
if((mask & 8) != 0 && (last_mask & 4) == 0)
{
++nr;
}
if((mask & 8) != 0 && (last_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 |
504 ms |
988 KB |
Output isn't correct |
| 4 |
Execution timed out |
1035 ms |
2392 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
348 KB |
Output isn't correct |
| 3 |
Incorrect |
104 ms |
2988 KB |
Output isn't correct |
| 4 |
Incorrect |
350 ms |
3744 KB |
Output isn't correct |
| 5 |
Execution timed out |
691 ms |
4824 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1044 ms |
6228 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
464 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 5 |
Incorrect |
20 ms |
500 KB |
Output isn't correct |
| 6 |
Incorrect |
19 ms |
348 KB |
Output isn't correct |
| 7 |
Incorrect |
59 ms |
604 KB |
Output isn't correct |
| 8 |
Execution timed out |
1006 ms |
1524 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1018 ms |
2132 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1043 ms |
5700 KB |
Time limit exceeded |
