QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#127007	#6636. Longest Strictly Increasing Sequence	oreoioiwy^#	AC ✓	1ms	3692kb	C++14	1.6kb	2023-07-19 12:15:38	2023-07-19 12:15:41

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-07-19 12:15:41]
评测

测评结果：AC
用时：1ms
内存：3692kb

查看

[2023-07-19 12:15:38]
提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// #define tpyeinput int
// inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
// inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}

template<typename T>
void read(T &x) {
    int f = 1;
    x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch ^ 48);
        ch = getchar();
    }
    x *= f;
}

const int N = 1e6+10, M = 2*N;

void solve() {
    int n;
    read(n);
    vector<int> a(n+1);
    vector<int> ans;
    for(int i = 1; i <= n; ++i) {
        read(a[i]);
    }
    int pre = 0, cnt = 0;
    if(a[1] != 1){
        puts("NO");
        return;
    }
    ans.push_back(1);
    pre = 1;
    cnt = 1;
    for(int i = 2; i <= n; i++) {
        if(a[i] < pre || a[i] > pre+1) {
            puts("NO");
            return;
        }
        else if(a[i] == pre) {
            ans.push_back(pre);
        }
        else {
            ans.push_back(pre+1);
            pre++;
        }
    }
    puts("YES");
    for(int i = 0; i < n; i++) {
        if(i) printf(" ");
        printf("%d", ans[i]);
    }
    puts("");
}

int main() {
#ifdef LOCAL_TEST
    freopen("test.in", "r", stdin);
#endif
    int times = 1;
    read(times);
    while(times--) {
        solve();   
    }
    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: 3620kb

input:

2
6
1 2 3 2 5 7
2
1 2

output:

NO
YES
1 2

result:

ok t=2 (2 test cases)

Test #2:

score: 0

Accepted

time: 0ms

memory: 3692kb

input:

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

output:

NO
NO
YES
1 2 3 4 4 5 6 6 6 7
YES
1 1 2 2 2 2 3 4 4 5
NO
NO
NO
YES
1 2 2 2 2 2 2 3 3 3
YES
1 1 2 3 4 5 5 5 5 6
YES
1 2 3 4 5 5 6 6 7
NO
NO
YES
1 2 3 3 3 3 4 4 4 5
NO
NO
YES
1 2 2 3 4 4 4 4 5 5
NO
NO
NO
NO
NO
NO
YES
1 1 1 2 2 3 3 4 4
NO
NO
NO
NO
NO
NO
NO
YES
1 2 3 3 3 4 4 4 5 5
YES
1 1 2 2 2 3 3 3 3 ...

result:

ok t=3483 (3483 test cases)