Submission #440754

#	Time	Username	Problem	Language	Result	Execution time	Memory
440754		training4usaco	Longest beautiful sequence (IZhO17_subsequence)	C++11	Compilation error	0 ms	0 KiB

subsequence

#include <iostream>
#include <vector>
using namespace std;

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

    vector<int> a(n + 1), k(n + 1);

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

    vector<int> dp(n + 1);
    vector<int> from(n + 1);

    vector<vector<vector<int>>> store(1 << 10, vector<vector<int>>(1 << 10, vector<int>(11)));
    // best index if we have a mask for the first 10 bits and a mask for the second 10 bits and we need i setbits in the first 10

    for(int i = 1; i <= n; ++i) {
        int lmask = a[i] >> 10; // top mask
        int rmask = a[i] & ((1 << 10) - 1);  // bottom mask

        int best = 0;
        for(int m = 0; m < (1 << 10); ++i) {
            int numset = 0;
            for(int j = 0; j < 20; ++j) {
                if((m & rmask) & (1 << j)) {
                    ++numset;
                }
            }
            int need = k[i] - numset;

            if(need > 10 || need < 0) {
                continue;
            }

            if(dp[best] < dp[store[lmask][m][need]]) {
                best = store[lmask][m][need];
            }
        }

        dp[i] = 1 + dp[best];
        from[i] = best;

        for(int m = 0; m < (1 << 10); ++m) {
            int numset = 0;
            for(int j = 0; j < 20; ++j) {
                if((m & lmask) & (1 << j)) {
                    ++numset;
                }
            }
            
            if(dp[store[m][rmask][numset]] < dp[i]) {
                store[m][rmask][numset] = i;
            }
        }
    }

    int highest = 1;
    for(int i = 1; i <= n; ++i) {
        if(dp[highest] < dp[i]) {
            highest = i;
        }
    }

    vector<int> answer;
    while(highest) {
        answer.push_back(highest);
        highest = from[highest];
    }

    sort(answer.begin(), answer.end());
    cout << answer.size() << endl;
    for(int i = 0; i < answer.size(); ++i) {
        cout << answer[i] << " ";
    }
    cout << endl;

    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:77:5: error: 'sort' was not declared in this scope; did you mean 'qsort'?
   77 |     sort(answer.begin(), answer.end());
      |     ^~~~
      |     qsort
subsequence.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 0; i < answer.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~~~