QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#122565	#6636. Longest Strictly Increasing Sequence	installb^#	AC ✓	10ms	3568kb	C++14	2.7kb	2023-07-10 19:18:02	2023-07-10 19:18:04

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-10 19:18:04]
评测

测评结果：AC
用时：10ms
内存：3568kb

查看

[2023-07-10 19:18:02]
提交

answer

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

vector <pair <ll,ll> > lis;

// void init(){
//     int a[15],f[15];
//     for(int i = 1;i <= 10;i ++) a[i] = i;
//     do{
//         ll S = 0,T = 0;
//         for(int i = 1;i <= 10;i ++){
//             f[i] = 1;
//             for(int j = 1;j < i;j ++){
//                 if(a[j] < a[i]) f[i] = max(f[i],f[j] + 1);
//             }
//             S = 10ll * S + (f[i] - 1);
//             T = 10ll * T + (a[i] - 1);
//         }
//         lis.push_back({S,T});
//     }while(next_permutation(a + 1,a + 1 + 10));
//     sort(lis.begin(),lis.end());
// }

int a[15],f[15],g[15];
// int vis[15];
// void dfs(int dep){
//     if(dep > 10){
//         ll S = 0,T = 0;
//         for(int i = 1;i <= 10;i ++){
//             S = 10ll * S + (g[i] - 1);
//             T = 10ll * T + (a[i] - 1);
//         }
//         lis.push_back({S,T});
//     }
//     for(int i = 1;i <= 10;i ++){
//         if(vis[i]) continue;
//         vis[i] = 1;
//         a[dep] = i; f[dep] = 1; g[dep] = 1;
//         for(int j = dep - 1;j >= 1;j --){
//             if(a[j] < a[dep]) f[dep] = max(f[dep],f[j] + 1);
//             g[dep] = max(g[dep],f[j]);
//         }
//         g[dep] = max(g[dep],f[dep]);
//         dfs(dep + 1);
//         vis[i] = 0;
//     }
// }

void solve(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    for(int i = 1;i <= n;i ++){
        f[i] = g[i] = 1;
        for(int j = 1;j < i;j ++){
            if(a[j] < a[i]) f[i] = max(f[i],f[j] + 1);
        }
        g[i] = max(f[i],g[i - 1]);
        if(g[i] != a[i]){
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
    for(int i = 1;i <= n;i ++) cout << a[i] << " \n"[i == n];
    // int n; ll S = 0;
    // cin >> n;
    // int w;
    // for(int i = 1;i <= 10;i ++){
    //     if(i <= n) cin >> w;
    //     S = 10ll * S + (w - 1);
    // }
    // // cout << S << endl;
    // int x = lower_bound(lis.begin(),lis.end(),pair <ll,ll>({S,-1})) - lis.begin();
    // if(x >= lis.size() || lis[x].first != S){
    //     cout << "NO\n";
    //     return;
    // }
    // ll T = lis[x].second;
    // cout << "YES\n";
    // vector <int> G;
    // for(int i = 1;i <= 10;i ++){
    //     G.push_back(T % 10 + 1);
    //     T /= 10;
    // }
    // reverse(G.begin(),G.end());
    // for(int i = 0;i < n;i ++) cout << G[i] << " \n"[i == n - 1];
}

int main(){
    ios::sync_with_stdio(false);
    // dfs(1);
    // sort(lis.begin(),lis.end());
    int TC;
    cin >> TC;
    while(TC --){
        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: 3568kb

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: 10ms

memory: 3404kb

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)