QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#366862#8228. 排序Wuyanru100 ✓1513ms16252kbC++143.0kb2024-03-25 11:20:382024-03-25 11:20:38

Judging History

This is the latest submission verdict.

  • [2024-03-25 11:20:38]
  • Judged
  • Verdict: 100
  • Time: 1513ms
  • Memory: 16252kb
  • [2024-03-25 11:20:38]
  • Submitted

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