Submission #964989

#	Time	Username	Problem	Language	Result	Execution time	Memory
964989		mgch	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	1 ms	348 KiB

subsequence

//and you'll find not what you searched and not where you searched (c) just tell what to incapsulate
//be yourself - do your best, learn self-taught through learning
#include <bits/stdc++.h>

using namespace std;

const int N = 5005, MOD = 1000000007;

bitset <N> D[N];

int main() {
//    freopen("input.txt", "r", stdin);
    freopen("subsequence.in", "r", stdin); freopen("subsequence.out", "w", stdout);
    int n;
    scanf("%d", &n);
    vector <int> a(n), k(n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    for (int i = 0; i < n; ++i) scanf("%d", &k[i]); //purpose of k[0]
    pair <int, int> ans = make_pair(-1, 0);
    for (int i = 0; i < n; ++i) {
        D[i].set(0);
        for (int j = D[i]._Find_first(); j <= i; j = D[i]._Find_next(j)) {
            if (ans.first < j + 1) {
                ans = make_pair(j + 1, i);
            }
            for (int l = i + 1; l < n; ++l) {//n-l+j>ans.first
                if (__builtin_popcount(a[i] & a[l]) == k[j + 1]) {
                    D[l].set(j + 1);
                }
            }
        }
    }
    cout << ans.first << '\n';
    vector <int> res;
    for (int i = ans.first; i > 0; --i) {
        res.push_back(ans.second);
        for (int j = ans.second - 1; j >= 0; --j) {
            if (__builtin_popcount(a[j] & a[ans.second]) == k[ans.first - 1]) {
                ans.second = j;
                --ans.first;
                break;
            }
        }
    }
    for (int i = 0; i < (int)res.size(); ++i) {
        cout << res[(int)res.size() - 1 - i] + 1 << " \n"[i == (int)res.size() - 1];
    }
    cout << '\n';
    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen("subsequence.in", "r", stdin); freopen("subsequence.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:13:51: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen("subsequence.in", "r", stdin); freopen("subsequence.out", "w", stdout);
      |                                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
subsequence.cpp:17:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
      |                                 ~~~~~^~~~~~~~~~~~~
subsequence.cpp:18:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     for (int i = 0; i < n; ++i) scanf("%d", &k[i]); //purpose of k[0]
      |                                 ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60