Fu_L's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Fu-L/cp-library

:heavy_check_mark: verify/unit_test/dp/longest_increasing_sequence.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "../../../src/template/template.hpp"
#include "../../../src/dp/longest_increasing_sequence.hpp"
int brute_length(const vector<int>& a) {
    const int n = (int)a.size();
    int res = 0;
    for(int bit = 0; bit < (1 << n); ++bit) {
        vector<int> b;
        for(int i = 0; i < n; ++i) {
            if((bit >> i) & 1) b.push_back(a[i]);
        }
        bool ok = true;
        for(int i = 1; i < (int)b.size(); ++i) {
            if(b[i - 1] >= b[i]) ok = false;
        }
        if(ok) res = max(res, (int)b.size());
    }
    return res;
}
void check(const vector<int>& a) {
    const vector<int> lis = longest_increasing_sequence(a);
    assert((int)lis.size() == brute_length(a));
    for(int i = 0; i < (int)lis.size(); ++i) {
        assert(0 <= lis[i] and lis[i] < (int)a.size());
        if(i) {
            assert(lis[i - 1] < lis[i]);
            assert(a[lis[i - 1]] < a[lis[i]]);
        }
    }
}
int main() {
    check({});
    check({3, 2, 1});
    check({1, 1, 1});
    check({3, 1, 2, 1, 4});
    for(int n = 0; n <= 10; ++n) {
        const int total = 1 << n;
        for(int bit = 0; bit < total; ++bit) {
            vector<int> a(n);
            for(int i = 0; i < n; ++i) a[i] = ((bit >> i) & 1) ? 1 : 0;
            check(a);
        }
    }
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
}
#line 1 "verify/unit_test/dp/longest_increasing_sequence.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
#line 4 "src/template/template.hpp"
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/dp/longest_increasing_sequence.hpp"
template <typename T>
vector<int> longest_increasing_sequence(const vector<T>& a) {
    const int n = a.size();
    if(n == 0) return {};
    vector<pair<T, int>> dp;
    vector<int> p(n, -1);
    for(int i = 0; i < n; ++i) {
        auto it = lower_bound(begin(dp), end(dp), make_pair(a[i], -i));
        if(it != begin(dp)) p[i] = -prev(it)->second;
        if(it == end(dp)) {
            dp.emplace_back(a[i], -i);
        } else {
            *it = make_pair(a[i], -i);
        }
    }
    vector<int> res;
    for(int i = -dp.back().second; i != -1; i = p[i]) res.push_back(i);
    reverse(begin(res), end(res));
    return res;
}
#line 4 "verify/unit_test/dp/longest_increasing_sequence.test.cpp"
int brute_length(const vector<int>& a) {
    const int n = (int)a.size();
    int res = 0;
    for(int bit = 0; bit < (1 << n); ++bit) {
        vector<int> b;
        for(int i = 0; i < n; ++i) {
            if((bit >> i) & 1) b.push_back(a[i]);
        }
        bool ok = true;
        for(int i = 1; i < (int)b.size(); ++i) {
            if(b[i - 1] >= b[i]) ok = false;
        }
        if(ok) res = max(res, (int)b.size());
    }
    return res;
}
void check(const vector<int>& a) {
    const vector<int> lis = longest_increasing_sequence(a);
    assert((int)lis.size() == brute_length(a));
    for(int i = 0; i < (int)lis.size(); ++i) {
        assert(0 <= lis[i] and lis[i] < (int)a.size());
        if(i) {
            assert(lis[i - 1] < lis[i]);
            assert(a[lis[i - 1]] < a[lis[i]]);
        }
    }
}
int main() {
    check({});
    check({3, 2, 1});
    check({1, 1, 1});
    check({3, 1, 2, 1, 4});
    for(int n = 0; n <= 10; ++n) {
        const int total = 1 << n;
        for(int bit = 0; bit < total; ++bit) {
            vector<int> a(n);
            for(int i = 0; i < n; ++i) a[i] = ((bit >> i) & 1) ? 1 : 0;
            check(a);
        }
    }
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
}
Back to top page