QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #243404 | #7729. Permutation Compression II | tnos# | WA | 52ms | 5840kb | C++14 | 717b | 2023-11-08 10:10:04 | 2023-11-08 10:10:05 |
Judging History
answer
#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
using Yukinoshita Yukino;
int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int mxn=1e6+5;
int a[mxn],stk[mxn];
bool vis[mxn];
int main()
{
int T=read();
while(T--)
{
int n=read(),i,top=0,cnt=0;
memset(vis,0,n+1);
for(i=1;i<=n;i++)
a[i]=read();
for(i=n;i;i--)
{
if(top&&a[stk[top]]<a[i]) vis[i]=1,cnt++;
for(;top&&a[stk[top]]<a[i];top--);
stk[++top]=i;
}
printf("%d %d\n",n-cnt,cnt);
for(i=1;i<=n;i++)
if(vis[i])
printf("%d ",i);
puts("");
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5840kb
input:
2 3 3 1 2 3 1 2 3
output:
2 1 1 3 0
result:
ok ok n = 3
Test #2:
score: -100
Wrong Answer
time: 52ms
memory: 5780kb
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:
5 2 3 5 4 2 3 4 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 19 14 3 5 8 9 12 13 17 18 20 22 24 26 27 29 1 1 1 2 1 2 1 0 2 2 1 2 8 6 3 6 7 8 10 12 3 2 2 3 8 8 3 4 5 7 8 9 11 13 3 1 1 2 3 2 3 4 6 2 1 4 1 1 1 4 4 1 3 5 7 2 0 4 5 1 2...
result:
wrong answer x is not prefix maximum