Submission #658389

#	Time	Username	Problem	Language	Result	Execution time	Memory
658389		sam571128	Volontiranje (COCI21_volontiranje)	C++17	110 / 110	290 ms	116652 KiB

Main

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long

using namespace std;

const int N = 1e6+5;
vector<int> num[N];
vector<vector<int>> ans;
int arr[N], dp[N];

signed main(){
    fastio
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }

    vector<int> lis;
    for(int i = 1; i <= n; i++){
        int idx = lower_bound(lis.begin(),lis.end(),arr[i])-lis.begin();
        if(idx==lis.size()) lis.push_back(arr[i]);
        else lis[idx] = arr[i];
        dp[i] = idx+1;
        num[idx+1].push_back(i);
    }

    int m = lis.size();
    for(int i = 1; i <= m; i++){
        reverse(num[i].begin(),num[i].end());
    }

    vector<int> tmp;
    int now = 1, idx = n+1;
    while(true){
        tmp.clear();
        for(int i = 1; i <= m; i++){
            while(!num[i].empty()){
                if(!tmp.empty()&&num[i].back() < tmp.back()) num[i].pop_back();
                else if(!tmp.empty() && arr[num[i].back()] < arr[tmp.back()]){
                    tmp.pop_back();
                    i -= 2;
                    goto popped;
                }
                else{
                    tmp.push_back(num[i].back());
                    num[i].pop_back();
                    break;
                }
            }
            if(tmp.size() < i){
                goto done;
            }
            popped:;
        }
        ans.push_back(tmp);
    }
    done:;

    cout << ans.size() << " " << m << "\n";
    for(auto v : ans){
        for(auto x : v){
            cout << x << " ";
        }
        cout << "\n";
    }
}   

/*
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:25:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         if(idx==lis.size()) lis.push_back(arr[i]);
      |            ~~~^~~~~~~~~~~~
Main.cpp:54:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   54 |             if(tmp.size() < i){
      |                ~~~~~~~~~~~^~~
Main.cpp:37:9: warning: unused variable 'now' [-Wunused-variable]
   37 |     int now = 1, idx = n+1;
      |         ^~~
Main.cpp:37:18: warning: unused variable 'idx' [-Wunused-variable]
   37 |     int now = 1, idx = n+1;
      |                  ^~~

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60