UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211508#1689. 合法的出栈序列zhoushouchen1002ms1172kbC++1.0kb2024-08-12 11:22:262024-08-12 11:22:27

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#include<stack>

inline int read()
{
    int r,s=0,c;
    for(;!isdigit(c=getchar());s=c);
    for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);
    return s^45?r:-r;
}

const int N=1000010;

int main()
{
    int n=read(),m=read();
    while(m--)
    {
        std::stack<int> st;
        while(!st.empty())st.pop();
        int pos=0;
        bool flag=0;
        for(int i=1;i<=n;++i)
        {
            int f=read();
            if(flag)
                continue;
            if(f>pos)
            {
                while(pos<f)
                    st.push(++pos);
                st.pop();
            }
            else
            {
                if(st.empty()||st.top()!=f)
                {
                    puts("NO");
                    flag=1;
                }
                else
                    st.pop();
            }
        }
        if(!flag)
            puts("YES");
    }



    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 20
Accepted
time: 1ms
memory: 1168kb

input:

13 61
12 11 10 9 8 7 6 5 4 3 2 1 13
11 13 12 10 9 8 7 6 5 4 3 2 1
11 12 13 10 9 8 7 6 5 4 3 2 1
11 1...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YE...

result:

ok 61 lines

Test #2:

score: 20
Accepted
time: 0ms
memory: 1172kb

input:

4 14
2 4 1 3
3 4 2 1
3 2 4 1
3 2 1 4
2 4 3 1
2 4 1 3
2 3 1 4
2 1 4 3
2 1 3 4
1 4 3 2
1 3 4 2
1 4 2 3...

output:

NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES

result:

ok 14 lines

Test #3:

score: 20
Accepted
time: 1ms
memory: 1168kb

input:

6 28
4 3 6 5 2 1
4 3 5 6 2 1
4 3 2 6 5 1
4 3 2 5 6 1
4 3 2 5 1 6
4 3 2 1 6 5
3 5 6 4 2 1
3 5 4 2 6 1...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES...

result:

ok 28 lines

Test #4:

score: 20
Accepted
time: 0ms
memory: 1168kb

input:

6 132
6 5 3 4 2 1
5 6 4 3 2 1
5 4 6 3 2 1
5 4 3 6 2 1
5 4 3 2 6 1
5 4 2 3 1 6
4 6 5 3 2 1
4 5 6 2 3 ...

output:

NO
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 132 lines

Test #5:

score: 20
Accepted
time: 0ms
memory: 1168kb

input:

10 54
10 9 8 4 6 5 7 3 2 1
9 10 8 7 6 5 4 3 2 1
9 8 10 7 6 5 4 3 2 1
9 8 7 10 6 5 4 3 1 2
9 8 7 6 10...

output:

NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES...

result:

ok 54 lines