Submission #69536700

---

Source Code Expand

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <atcoder/all>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;
using namespace atcoder;
typedef vector<int> Vec;

void printVec(Vec p, int baius) {
    int i;
    rep(i, p.size()) {
        cout << p[i] + baius;
        if (i + 1 < p.size()) cout << " ";
    }
    cout << endl;
}

int calc(Vec p) {
    int i, j, n = p.size();
    
    const int INF = 1e+9;
    Vec dp1(n + 1, INF), dp2(n + 1, INF);

    dp1[0] = -INF;
    dp2[0] = -INF;
    rep(i, n) {
        int it1 = lower_bound(dp1.begin(), dp1.end(), p[i]) - dp1.begin();
        int it2 = lower_bound(dp2.begin(), dp2.end(), -p[i]) - dp2.begin();
        dp1[it1] = p[i];
        dp2[it2] = -p[i];
    }
    
    int len1 = 0, len2 = 0;
    for (i = n; i >= 0; i--) if (dp1[i] < INF) { len1 = i; break; }
    for (i = n; i >= 0; i--) if (dp2[i] < INF) { len2 = i; break; }

    vector<bool> used_lis(n), used_lds(n); //value -> include?

    rep(i, (1 << n)) {
        Vec v;
        rep(j, n) {
            if ((i >> j) % 2) {
                v.push_back(p[j]);
            }
        }

        bool is_lis = true, is_lds = true;
        rep(j, ((int)v.size()) - 1) {
            if (v[j] > v[j + 1]) is_lis = false;
            if (v[j] < v[j + 1]) is_lds = false;    
        }

        if (is_lis && v.size() >= len1) {
            assert(v.size() == len1);
            rep(j, v.size()) used_lis[v[j]] = true;
        }

        if (is_lds && v.size() >= len2) {
            assert(v.size() == len2);
            rep(j, v.size()) used_lds[v[j]] = true;
        }
    }

    int cnt = 0;
    rep(i, n) {
        if (used_lis[i] && used_lds[i]) cnt++;
    }
    return cnt;
}

Vec solve(int n, int K) {
    int i;

    if (n <= 7) {
        Vec p(n);
        int i; rep(i, n) p[i] = i;
        do {
            int cnt = calc(p);
            if (cnt == K) return p;
        } while (next_permutation(p.begin(), p.end()));
        return Vec();
    }

    if (K == 0) {
        Vec a = {2, 3, 7, 6, 1, 0, 4, 5};
        Vec p;
        rep(i, n - 8) p.push_back(i);
        for (i = n - 8; i < n; i++) {
            p.push_back(n - 8 + a[i - (n - 8)]);
        }
        return p;
    }

    if (K == 1) {
        Vec a = {1, 4, 2, 0, 3};
        Vec p;
        rep(i, n - 5) p.push_back(i);
        for (i = n - 5; i < n; i++) {
            p.push_back(n - 5 + a[i - (n - 5)]);
        }
        return p;
    }

    if (K == n) {
        Vec p(n);
        int i; rep(i, n) p[i] = i;
        return p;
    }

    Vec a;
    a.push_back(0);
    rep(i, K) {
        a.push_back(K - i);
    }

    Vec p;
    rep(i, n - K - 1) {
        p.push_back(i);
    }

    int cor = 0;
    for (i = n - K - 1; i < n; i++) {
        p.push_back(a[cor] + (n - K - 1));
        cor++;
    }
    return p;
}

signed main() {
    int T;
    cin >> T;
    while (T--) {
        int n, K;
        cin >> n >> K;
        Vec a = solve(n, K);
        if (a.size() == 0) cout << -1 << endl;
        else printVec(a, 1);
    }
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void printVec(Vec, long long int)’:
Main.cpp:15:32: 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]
   15 | #define rep(i, n) for(i = 0; i < n; i++)
      |                                ^
Main.cpp:23:5: note: in expansion of macro ‘rep’
   23 |     rep(i, p.size()) {
      |     ^~~
Main.cpp:25:19: 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 (i + 1 < p.size()) cout << " ";
      |             ~~~~~~^~~~~~~~~~
Main.cpp: In function ‘long long int calc(Vec)’:
Main.cpp:65:32: 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]
   65 |         if (is_lis && v.size() >= len1) {
      |                       ~~~~~~~~~^~~~~~~
In file included from /usr/include/c++/12/cassert:44,
                 from /opt/ac-library/atcoder/twosat.hpp:4,
                 from /opt/ac-library/atcoder/twosat:1,
                 from /opt/ac-library/atcoder/all:12,
                 from Main.cpp:14:
Main.cpp:66:29: 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]
   66 |             assert(v.size() == len1);
      |                    ~~~~~~~~~^~~~~~~
Main.cpp:15:32: 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]
   15 | #define rep(i, n) for(i = 0; i < n; i++)
      |                                ^
Main.cpp:67:13: note: in expansion of macro ‘rep’
   67 |             rep(j, v.size()) used_lis[v[j]] = true;
      |             ^~~
Main.cpp:70:32: 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]
   70 |         if (is_lds && v.size() >= len2) {
      |                       ~~~~~~~~~^~~~~~~
Main.cpp:71:29: 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]
   71 |             assert(v.size() == len2);
      |                    ~~~~~~~~~^~~~~~~
Main.cpp:15:32: 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]
   15 | #define rep(i, n) for(i = 0; i < n; i++)
      |                                ^
Main.cpp:72:13: note: in expansion of macro ‘rep’
   72 |             rep(j, v.size()) used_lds[v[j]] = true;
      |             ^~~

Judge Result