2023 NAQ Solutions

A.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, c;
    cin >> n >> k >> c;

    map<int, int> cnt;
    vector<array<int, 3>> a;
    vector<array<int, 2>> ans;
    for (int i = 0; i < n; i++) {
        int t, s;
        cin >> t >> s;
        if (cnt[s] < c && (int)size(ans) < k) {
            cnt[s]++;
            ans.push_back({i, t});
        } else {
            a.push_back({i, t, s});
        }
    }

    if ((int)size(ans) < k) {
        int m = k - (int)size(ans);
        for (int i = 0; i < m; i++) {
            ans.push_back({a[i][0], a[i][1]});
        }
    }

    sort(begin(ans), end(ans));
    for (auto [i, t] : ans) {
        cout << t << '\n';
    }
    return 0;
}

B.cpp

#include <bits/stdc++.h>
template <typename T>
constexpr static T qpow(T a, int64_t b) {
    T res;
    if constexpr (std::is_arithmetic_v<T>) {
        res = 1;
    } else {
        res = a.identity();
    }
    while (b) {
        if (b & 1) {
            res = res * a;
        }
        b >>= 1;
        a = a * a;
    }
    return res;
}

template <typename T, T MOD>
struct ModInt {
    using prod_type = std::conditional_t<std::numeric_limits<T>::digits <= 32, uint64_t, __uint128_t>;
    T val;
    constexpr ModInt(const int64_t v = 0) : val(v % MOD) { if (val < 0) val += MOD; }
    constexpr ModInt operator+() const { return ModInt(val); }
    constexpr ModInt operator-() const { return ModInt(MOD - val); }
    constexpr ModInt inv() const {
        return qpow(*this, MOD - 2);
    }
    constexpr friend ModInt operator+(ModInt lhs, const ModInt rhs) { return lhs += rhs; }
    constexpr friend ModInt operator-(ModInt lhs, const ModInt rhs) { return lhs -= rhs; }
    constexpr friend ModInt operator*(ModInt lhs, const ModInt rhs) { return lhs *= rhs; }
    constexpr friend ModInt operator/(ModInt lhs, const ModInt rhs) { return lhs /= rhs; }
    constexpr ModInt &operator+=(const ModInt x) {
        if ((val += x.val) >= MOD)
            val -= MOD;
        return *this;
    }
    constexpr ModInt &operator-=(const ModInt x) {
        if ((val -= x.val) < 0)
            val += MOD;
        return *this;
    }
    constexpr ModInt &operator*=(const ModInt x) {
        val = prod_type(val) * x.val % MOD;
        return *this;
    }
    constexpr ModInt &operator/=(const ModInt x) { return *this *= x.inv(); }
    bool operator==(const ModInt b) const { return val == b.val; }
    bool operator!=(const ModInt b) const { return val != b.val; }
    friend std::istream &operator>>(std::istream &is, ModInt &x) noexcept {
        return is >> x.val;
    }
    friend std::ostream &operator<<(std::ostream &os, const ModInt x) noexcept {
        return os << x.val;
    }
    constexpr static ModInt identity() { return 1; }
    constexpr ModInt pow(int64_t p) {
        return qpow(*this, p);
    }
};
using ModInt1000000007 = ModInt<int, 1'000'000'007>;
using ModInt998244353 = ModInt<int, 998244353>;
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    using mint = ModInt<int, 9302023>;

    int n = (int)size(s);
    vector<int> mn(n + 1);
    vector<mint> cnt(n + 1);
    cnt[0] = 1;

    vector<string> words {
        "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"
    };

    for (int i = 0; i < n; i++) {
        mn[i + 1] = mn[i] + 1;
        cnt[i + 1] = cnt[i];

        for (const auto& w : words) {
            int len = size(w);
            if (i - len + 1 >= 0) {
                if (s.substr(i - len + 1, len) != w) continue;
                if (mn[i + 1 - len] + 1 < mn[i + 1]) {
                    mn[i + 1] = mn[i + 1 - len] + 1;
                    cnt[i + 1] = cnt[i + 1 - len];
                } else if (mn[i + 1 - len] + 1 == mn[i + 1]) {
                    cnt[i + 1] += cnt[i + 1 - len];
                }
            }
        }
    }

    cout << mn[n] << '\n' << cnt[n] << endl;
    return 0;
}

C.cpp

#include <bits/stdc++.h>
template<typename T> using min_heap = std::priority_queue<T, std::vector<T>, std::greater<>>;
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<array<int, 2>> a(n);
    for (auto& [x, y] : a) cin >> x >> y;


    auto check = [&](double m) {
        min_heap<pair<int, double>> q;
        for (int i = 0; i < n; i++) {
            if (a[i][0]) {
                q.emplace(a[i][1] - 1, a[i][0]);
            }
            while (!q.empty() && q.top().first < i) {
                q.pop();
            }

            if (q.empty()) {
                return false;
            }

            auto rem = m;
            while (rem > 0) {
                if (q.empty()) {
                    return false;
                }
                auto [d, x] = q.top();
                q.pop();
                double mn = min(x, rem);
                rem -= mn;
                x -= mn;
                if (x > 0) {
                    q.emplace(d, x);
                }
            }
        }
        return true;
    };

    if (!check(0)) {
        cout << "-1\n";
        return 0;
    }

    double l = 0, r = 1e9 / k;
    for (int it = 0; it < 60; it++) {
        double mid = (l + r) / 2;
        if (check(mid * k)) {
            l = mid;
        } else {
            r = mid;
        }
    }

    cout << fixed << setprecision(9) << l << endl;
    return 0;
}

E.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<array<int, 2>> a(n);
    for (auto& [l, r] : a) {
        cin >> l >> r;
        l--, r--;
    }

    vector<int> dp(n + 1);
    auto check = [&](int idx) {
        for (auto i : {idx - 2, idx - 1, idx}) {
            for (auto j : {idx - 2, idx - 1, idx}) {
                if (j == i) continue;
                if (j < a[i][0] || j > a[i][1]) return false;
            }
        }
        return true;
    };
    for (int i = 2; i < n; i++) {
        dp[i + 1] = dp[i];
        if (check(i)) {
            dp[i + 1] = dp[i - 2] + 1;
        }
    }

    cout << dp[n] << '\n';
    return 0;
}

F.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    set<char> vowel{'a', 'e', 'i', 'o', 'u'};
    int c1 = 0, c2 = 0;
    for (auto c : s) {
        if (vowel.count(c)) {
            c1++;
        } else if (c == 'y') {
            c2++;
        }
    }

    cout << c1 << ' ' << c1 + c2 << endl;
    return 0;
}

G.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, l;
    cin >> n >> l;
    l *= 5;

    vector<int> a(n);
    for (auto& x : a) cin >> x;
    sort(begin(a), end(a));

    int ans = 0;
    for (auto x : a) {
        if (l - x >= 0) {
            ans++;
            l -= x;
        }
    }

    cout << ans << endl;
    return 0;
}

H.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n, k, p;
    cin >> n >> k >> p;

    vector<ll> ans;
    for (ll f = 1; f * f <= n; f++) {
        if (n % f == 0) {
            if (f <= k && n / f <= p) {
                ans.push_back(f);
            }
            if (n / f != f) {
                if (n / f <= k && f <= p) {
                    ans.push_back(n / f);
                }
            }
        }
    }

    sort(begin(ans), end(ans));
    cout << size(ans) << '\n';
    for (auto x : ans) cout << x << '\n';
    return 0;
}

I.cpp

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void test_case() {
    string s;
    cin >> s;
    const int n = (int)size(s);

    vector<int> ans;
    auto check = [&](int x) {
        int bkp = x;
        int p = 0;
        int missing = -1;
        while (p < n) {
            string sx = to_string(x);
            if (s.substr(p, size(sx)) == sx) {
                x++;
                p += size(sx);
            } else {
                if (missing != -1) return;
                else {
                    missing = x;
                    x++;
                }
            }
        }

        assert(p == n);
        if (missing == -1) {
            if (bkp > 1) ans.push_back(bkp - 1);
            if (x <= 99999) ans.push_back(x);
        } else {
            ans.push_back(missing);
        }
        return;
    };

    for (int i = 1; i <= min(5, (int)size(s)); i++) {
        check(stoi(s.substr(0, i)));
    }

    sort(begin(ans), end(ans));
    ans.erase(unique(begin(ans), end(ans)), end(ans));

    cout << size(ans) << '\n';
    for (auto x : ans) cout << x << ' ';
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        test_case();
    }
}

J.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template <typename T> struct Trie {
    struct node {
        int cnt = 0;
        std::map<T, int> child;

        ostream& operator<<(ostream& o) const {
            return o;
        }
    };

    std::vector<node> t;

    Trie() { new_node(); }

    int new_node() {
        t.emplace_back();
        return (int)t.size() - 1;
    }

    template <typename S> void insert(const S &s) {
        int p = 0;
        for (const auto &c : s) {
            if (!t[p].child.count(c)) {
                t[p].child[c] = new_node();
            }
            p = t[p].child[c];
        }
        t[p].cnt = 1;
    }

    template <typename S> int find(const S &s) {
        int p = 0;
        for (auto ch : s) {
            if (!t[p].child.count(ch)) {
                return false;
            }
            p = t[p].child[ch];
        }
        return t[p].cnt;
    }

    void build() {
        for (int i = (int)size(t) - 1; i > 0; i--) {
            for (auto [c, v] : t[i].child) {
                t[i].cnt += t[v].cnt;
            }
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;

    Trie<char> pre, suf;
    Trie<array<char, 2>> both;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int len = (int)size(s);
        pre.insert(s);

        vector<array<char, 2>> p(len);
        for (int j = 0; j < len; j++) {
            p[j] = {s[j], s[len - 1 - j]};
        }
        both.insert(p);

        reverse(begin(s), end(s));
        suf.insert(s);
    }

    pre.build();
    suf.build();
    both.build();

    while (q--) {
        string op, s, t;
        cin >> op >> s >> t;
        reverse(begin(t), end(t));

        int len = (int)size(s);
        vector<array<char, 2>> p(len);
        for (int j = 0; j < len; j++) {
            p[j] = {s[j], t[j]};
        }

        auto c = both.find(p);
        auto u = pre.find(s) + suf.find(t);
        if (op[0] == 'A') {
            cout << c << '\n';
        } else if (op[0] == 'O') {
            cout << (u - c) << '\n';
        } else if (op[0] == 'X') {
            cout <<(u - c * 2) << '\n';
        }
    }
    return 0;
}

L.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, mn, mx;
    cin >> n >> mn >> mx;

    int hit_mn = 0, hit_mx = 0;
    for (int i = 0; i < n - 1; i++) {
        int x;
        cin >> x;
        if (x == mn) hit_mn = 1;
        else if (x == mx) hit_mx = 1;
    }

    if (!hit_mn && !hit_mx) {
        cout << "-1\n";
    } else if (!hit_mn) {
        cout << mn << endl;
    } else if (!hit_mx) {
        cout << mx << endl;
    } else {
        for (int i = mn; i <= mx; i++) {
            cout << i << '\n';
        }
    }
    return 0;
}