Submission #704173

#	Time	Username	Problem	Language	Result	Execution time	Memory
704173		Username4132	Volontiranje (COCI21_volontiranje)	C++14	0 / 110	14 ms	23824 KiB

Main

#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 (stderr)

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
• Subtask 2: 0 / 40
• Subtask 3: 0 / 60