oj.uz

Submission #704107

# Submission time Handle Problem Language Result Execution time Memory
704107 2023-03-01T15:20:21 Z Username4132 Volontiranje (COCI21_volontiranje) C++14
0 / 110
 14 ms 23836 KB 
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define PB push_back

const int MAXN=1000010, INF=1000000000;
int n, arr[MAXN], brr[MAXN], rle[MAXN], rri[MAXN], d[MAXN], key[MAXN], lans;
vector<int> anti[MAXN];
vector<vector<int>> ret;

void lis(int* arg, int* res){
    forn(i, n+1) d[i]=INF;
    forn(i, n) res[i]=-1;
    d[0]=-INF;
    forn(i, n){
        auto itr = upper_bound(d, d+n+1, arg[i]);
        if(*itr>arg[i]){
            res[i]=itr-d;
            *itr=arg[i];
        }
    }
}

int main(){
    scanf("%d", &n);
    forn(i, n) scanf("%d", &arr[i]), brr[n-1-i]=n-arr[i];
    lis(arr, rle);    
    lis(brr, rri);
    forn(i, n) lans=max(lans, rle[i]);
    forn(i, n) key[i]= (rle[i] + rri[n-1-i] == lans+1)? rle[i] : -1;

    forn(i, n) if(key[i]!=-1) anti[key[i]-1].PB(i);
    while(true){
        vector<int> add;
        forn(i, lans){
            add.PB(anti[i].back());
            anti[i].pop_back();
        }
        ret.PB(add);
        if(anti[0].empty()) goto end;
        forn(i, lans-1){
            while(!anti[i+1].empty() && anti[i+1].back()<anti[i].back()){
                anti[i+1].pop_back();
            }
            if(anti[i+1].empty()) goto end;
        }
    }

    end:
    printf("%d %d\n", (int)ret.size(), lans);
    for(auto vec:ret){
        for(auto el:vec) printf("%d ", el+1);
        printf("\n");
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:29:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     forn(i, n) scanf("%d", &arr[i]), brr[n-1-i]=n-arr[i];
      |                ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23744 KB Output is correct
4 Correct 12 ms 23808 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 12 ms 23792 KB Output is correct
8 Correct 12 ms 23788 KB Output is correct
9 Correct 12 ms 23748 KB Output is correct
10 Correct 14 ms 23764 KB Output is correct
11 Correct 14 ms 23836 KB Output is correct
12 Incorrect 12 ms 23764 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23744 KB Output is correct
4 Correct 12 ms 23808 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 12 ms 23792 KB Output is correct
8 Correct 12 ms 23788 KB Output is correct
9 Correct 12 ms 23748 KB Output is correct
10 Correct 14 ms 23764 KB Output is correct
11 Correct 14 ms 23836 KB Output is correct
12 Incorrect 12 ms 23764 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23744 KB Output is correct
4 Correct 12 ms 23808 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 12 ms 23792 KB Output is correct
8 Correct 12 ms 23788 KB Output is correct
9 Correct 12 ms 23748 KB Output is correct
10 Correct 14 ms 23764 KB Output is correct
11 Correct 14 ms 23836 KB Output is correct
12 Incorrect 12 ms 23764 KB Output isn't correct
13 Halted 0 ms 0 KB -