QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#366862 | #8228. 排序 | Wuyanru | 100 ✓ | 1513ms | 16252kb | C++14 | 3.0kb | 2024-03-25 11:20:38 | 2024-03-25 11:20:38 |
Judging History
answer
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int mod=1000000007;
int ma[1048600];
ll dp[1048600];
int c1[12][12];
int b[12][31];
int a[31];
int c[31];
int d[15];
int n,m;
inline int get(int sta)
{
int ans=0;
for(int i=0;i<d[1];i++)
{
int c1=0,c2=0;
for(int j=i;j<n;j+=d[1])
{
c1++;
if(sta&(1<<j))
{
c2++;
if(c2!=c1) return -1;
}
}
ans=ans*(c1+1)+c2;
}
return ans;
}
inline int push(int sta)
{
for(int i=d[1]-1;i>=0;i--)
{
int c=(n-i+d[1]-1)/d[1];
int p=sta%(c+1);sta/=c+1;
for(int j=i,now=1;j<n;j+=d[1],now++) a[j]=now<=p;
}
memcpy(c,a,sizeof(c));
for(int i=2;i<=m;i++)
{
// printf("i=%d : \n",i);
// for(int j=0;j<n;j++) printf("%d%c",c[j]," \n"[j==n-1]);
for(int j=0;j<d[i];j++)
{
int c0=0,c1=0;
for(int k=j;k<n;k+=d[i])
{
b[i][k]=c0;
// printf("b[%d][%d]=%d\n",i,k,c0);
if(c[k]) c1++;else c0++;
}
// printf("j=%d c1=%d\n",j,c1);
for(int k=j,now=1;k<n;k+=d[i],now++) c[k]=now<=c1;
::c1[i][j]=c1;
}
}
int val=0;
for(int i=0;i<n;i++) val|=a[i]<<i;
return val;
}
inline void run(int sta)
{
int real=push(sta);
// printf("run %d(%d,%lld) : real=%d\n",sta,ma[sta],dp[sta],real);
// for(int i=0;i<n;i++) printf("%d%c",a[i]," \n"[i==n-1]);
for(int i=0;i<n;i++) if(!a[i]&&get(real|(1<<i))!=-1)
{
int val=0,now=i;
for(int j=2;j<=m;j++)
{
// printf("j=%d now=%d\n",j,now);
val+=b[j][now];
now=(now%d[j])+c1[j][now%d[j]]*d[j];
}
int to=get(real|(1<<i)),v=ma[sta]+val;
// printf("%d -> %d(%d) (%d,%d)\n",sta,to,real|(1<<i),v,ma[to]);
if(v>ma[to]) ma[to]=v,dp[to]=0;
if(v==ma[to]) dp[to]=(dp[to]+dp[sta])%mod;
}
}
inline int g1()
{
int ans=0;
for(int i=0;i<d[1];i++)
{
int c=0;
for(int j=i;j<n;j+=d[1]) c++;
ans+=c*(c-1)/2;
}
return ans;
}
int main()
{
// freopen("data.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=m;i++)
{
d[i]=read();
if(d[i]>=n) i--,m--;
}
memset(ma,-1,sizeof(ma));
ma[get(0)]=0,dp[get(0)]=1;
int N=get((1<<n)-1);
for(int i=0;i<=N;i++) run(i);
printf("%d %lld\n",ma[N]+g1(),dp[N]);
return 0;
}
/*
5 4
5 4 2 1
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 18
Accepted
Test #1:
score: 18
Accepted
time: 1ms
memory: 8956kb
input:
2 2 2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 8176kb
input:
5 4 5 4 2 1
output:
6 4
result:
ok 2 number(s): "6 4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 8796kb
input:
8 4 6 3 2 1
output:
15 4
result:
ok 2 number(s): "15 4"
Test #4:
score: 0
Accepted
time: 1ms
memory: 9148kb
input:
8 6 8 7 5 4 2 1
output:
14 2
result:
ok 2 number(s): "14 2"
Test #5:
score: 0
Accepted
time: 1ms
memory: 7960kb
input:
8 3 8 7 1
output:
22 7
result:
ok 2 number(s): "22 7"
Test #6:
score: 0
Accepted
time: 0ms
memory: 9396kb
input:
8 1 1
output:
28 1
result:
ok 2 number(s): "28 1"
Subtask #2:
score: 27
Accepted
Dependency #1:
100%
Accepted
Test #7:
score: 27
Accepted
time: 2ms
memory: 9564kb
input:
16 2 6 1
output:
77 15
result:
ok 2 number(s): "77 15"
Test #8:
score: 0
Accepted
time: 11ms
memory: 9696kb
input:
16 8 10 9 8 7 6 5 4 1
output:
57 5
result:
ok 2 number(s): "57 5"
Test #9:
score: 0
Accepted
time: 12ms
memory: 9088kb
input:
16 10 10 9 8 7 6 5 4 3 2 1
output:
57 3
result:
ok 2 number(s): "57 3"
Test #10:
score: 0
Accepted
time: 7ms
memory: 9164kb
input:
16 7 10 9 8 6 5 4 1
output:
49 1
result:
ok 2 number(s): "49 1"
Test #11:
score: 0
Accepted
time: 3ms
memory: 8500kb
input:
16 4 7 6 2 1
output:
52 9
result:
ok 2 number(s): "52 9"
Subtask #3:
score: 21
Accepted
Dependency #2:
100%
Accepted
Test #12:
score: 21
Accepted
time: 3ms
memory: 8548kb
input:
22 3 5 3 1
output:
100 1
result:
ok 2 number(s): "100 1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 8716kb
input:
22 1 1
output:
231 1
result:
ok 2 number(s): "231 1"
Test #14:
score: 0
Accepted
time: 73ms
memory: 8728kb
input:
22 4 10 8 3 1
output:
97 4
result:
ok 2 number(s): "97 4"
Test #15:
score: 0
Accepted
time: 86ms
memory: 9768kb
input:
22 5 10 7 6 3 1
output:
92 70
result:
ok 2 number(s): "92 70"
Test #16:
score: 0
Accepted
time: 92ms
memory: 9824kb
input:
22 6 10 9 8 7 3 1
output:
97 1
result:
ok 2 number(s): "97 1"
Test #17:
score: 0
Accepted
time: 125ms
memory: 9948kb
input:
22 10 10 9 8 7 6 5 4 3 2 1
output:
109 1
result:
ok 2 number(s): "109 1"
Subtask #4:
score: 10
Accepted
Test #18:
score: 10
Accepted
time: 3ms
memory: 8292kb
input:
14 2 10 1
output:
61 210
result:
ok 2 number(s): "61 210"
Test #19:
score: 0
Accepted
time: 1ms
memory: 9424kb
input:
18 2 2 1
output:
117 1
result:
ok 2 number(s): "117 1"
Test #20:
score: 0
Accepted
time: 352ms
memory: 14060kb
input:
30 2 9 1
output:
264 84
result:
ok 2 number(s): "264 84"
Test #21:
score: 0
Accepted
time: 275ms
memory: 14104kb
input:
29 2 9 1
output:
253 36
result:
ok 2 number(s): "253 36"
Test #22:
score: 0
Accepted
time: 46ms
memory: 12032kb
input:
25 2 8 1
output:
195 8
result:
ok 2 number(s): "195 8"
Subtask #5:
score: 24
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #23:
score: 24
Accepted
time: 954ms
memory: 16072kb
input:
30 4 10 9 5 1
output:
188 40
result:
ok 2 number(s): "188 40"
Test #24:
score: 0
Accepted
time: 1407ms
memory: 16128kb
input:
30 9 10 9 8 7 6 5 4 3 1
output:
184 6
result:
ok 2 number(s): "184 6"
Test #25:
score: 0
Accepted
time: 1293ms
memory: 16252kb
input:
30 8 10 9 8 7 4 3 2 1
output:
154 1
result:
ok 2 number(s): "154 1"
Test #26:
score: 0
Accepted
time: 1305ms
memory: 16044kb
input:
30 8 10 8 7 6 5 4 3 1
output:
155 1
result:
ok 2 number(s): "155 1"
Test #27:
score: 0
Accepted
time: 1129ms
memory: 16108kb
input:
30 6 10 8 6 4 3 1
output:
150 4
result:
ok 2 number(s): "150 4"
Test #28:
score: 0
Accepted
time: 1513ms
memory: 16128kb
input:
30 10 10 9 8 7 6 5 4 3 2 1
output:
184 6
result:
ok 2 number(s): "184 6"
Test #29:
score: 0
Accepted
time: 807ms
memory: 16080kb
input:
29 6 10 9 7 5 3 1
output:
129 200
result:
ok 2 number(s): "129 200"
Extra Test:
score: 0
Extra Test Passed