Submission #704107

#	Time	Username	Problem	Language	Result	Execution time	Memory
704107		Username4132	Volontiranje (COCI21_volontiranje)	C++14	0 / 110	14 ms	23836 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;
    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 (stderr)

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