oj.uz

Submission #704173

# Submission time Handle Problem Language Result Execution time Memory
704173 2023-03-01T20:04:47 Z Username4132 Volontiranje (COCI21_volontiranje) C++14
0 / 110
 14 ms 23824 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;
    d[0]=-INF;
    forn(i, n){
        auto itr = upper_bound(d, d+n+1, arg[i]);
        res[i]=itr-d;
        *itr=arg[i];        
    }
}

bool drop(int pos){
    bool flag=false, untouched=false;
    while(untouched && !anti[pos].empty() && !anti[pos+1].empty()){
        untouched=true;
        if(anti[pos].back() > anti[pos+1].back()){
            untouched=false;
            flag=true;
            anti[pos].pop_back();
        }
        if(arr[anti[pos].back()] > arr[anti[pos+1].back()]){
            untouched=false;
            flag=true;
            anti[pos+1].pop_back();
        }
    }
    if(pos && flag) drop(pos-1);
    return flag;
}

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);
        forn(i, lans-1) while(drop(i));
        forn(i, lans) if(anti[i].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:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:45:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     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 23824 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23708 KB Output is correct
5 Correct 12 ms 23760 KB Output is correct
6 Correct 12 ms 23792 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 11 ms 23792 KB Output is correct
9 Correct 13 ms 23788 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Incorrect 14 ms 23764 KB Subsequence indices should be sorted
13 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23824 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23708 KB Output is correct
5 Correct 12 ms 23760 KB Output is correct
6 Correct 12 ms 23792 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 11 ms 23792 KB Output is correct
9 Correct 13 ms 23788 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Incorrect 14 ms 23764 KB Subsequence indices should be sorted
13 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23824 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23708 KB Output is correct
5 Correct 12 ms 23760 KB Output is correct
6 Correct 12 ms 23792 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 11 ms 23792 KB Output is correct
9 Correct 13 ms 23788 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Incorrect 14 ms 23764 KB Subsequence indices should be sorted
13 Halted 0 ms 0 KB -