QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#244698	#7729. Permutation Compression II	AKCqhzdy	WA	105ms	5700kb	C++14	959b	2023-11-09 14:35:28	2023-11-09 14:35:28

Judging History

你现在查看的是最新测评结果

[2023-11-09 14:35:28]
评测

测评结果：WA
用时：105ms
内存：5700kb

查看

[2023-11-09 14:35:28]
提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int _=1e2;
const int maxn=1e6+_;

int f[maxn],h[maxn],a[maxn],p[maxn];

int asn,as[maxn];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;  int inf=(1<<30);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=0;i<=n+3;i++)f[i]=inf,h[i]=0,p[i]=0;  f[0]=0;

        int m=0;
        for(int i=1;i<=n;i++)
        {
            int g=lower_bound(f,f+m+2,a[i])-f;
            if(g>m)m=g;

            p[i]=h[m-1];
            if(f[m]>a[i])f[m]=a[i],h[m]=i;
        }

        int u=h[m];
        while(u)a[u]=-a[u],u=p[u];

        int now=0; asn=0;
        for(int i=1;i<=n;i++)
            if(a[i]<0)now=-a[u];
            else if(a[i]>now)as[++asn]=i;

        printf("%d %d\n",m,asn);
        for(int i=1;i<=asn;i++)printf("%d%c",as[i]," \n"[i==asn]);
    }

    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 5680kb

input:

output:

2 1
1
3 0

result:

ok ok n = 3

Test #2:

score: -100

Wrong Answer

time: 105ms

memory: 5700kb

input:

100000
7
2 6 7 1 4 3 5
6
1 5 6 3 2 4
3
1 2 3
3
2 1 3
14
9 6 13 10 4 7 5 14 1 12 8 3 2 11
3
1 2 3
14
1 9 3 14 5 7 4 6 12 2 8 11 13 10
8
7 1 3 6 2 5 8 4
16
9 3 4 8 7 16 10 6 11 1 14 2 13 12 5 15
3
3 1 2
33
9 10 23 3 16 1 19 32 25 4 5 31 28 7 22 27 30 8 6 17 2 14 13 29 20 33 26 18 24 11 12 15 21
2
2 1
...

output:

3 4
3 5 6 7
3 3
3 4 6
3 0
2 1
1
6 8
1 3 4 6 8 10 11 12
3 0
9 5
2 4 6 9 13
5 3
1 4 7
8 8
1 4 6 7 9 11 13 14
2 1
1
15 18
3 5 8 9 12 13 17 18 19 20 22 23 24 26 27 29 31 32
1 1
1
2 1
2
1 0
2 2
1 2
7 7
3 6 7 8 10 12 13
3 2
2 3
8 8
3 4 5 7 8 9 11 13
3 1
1
2 3
2 3 4
3 5
1 4 6 7 8
1 1
1
4 4
1 3 5 7
2 0
4 5
...

result:

wrong answer x is not prefix maximum