Submission #87286

#	Time	Username	Problem	Language	Result	Execution time	Memory
87286		Yaroslaff	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	5 ms	1144 KiB

subsequence

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define ll long long
#define it int
#define ld long double
#define endl '\n'
#define TIME 1.0*clock()/CLOCKS_PER_SEC

using namespace std;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

const int M = 1e9 + 7;
const int N = 1e5 + 7;

it n, x[N], k[N], kol[(1<<10)], dp[(1<<10)][(1<<10)][11], pr[(1<<10)][(1<<10)][11], ans = 0, pos = 0;

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#else
    freopen("subsequence.in","r",stdin);
    freopen("subsequence.out","w",stdout);
#endif
    vector<it> p(N, 0), res(N, 1);
    cin >> n;
    for (it i = 1; i <= n; i++)
        cin >> x[i];
    for (it i = 1; i <= n; i++)
        cin >> k[i];
    for (size_t i = 1; i <= n; i++){
        it a = (x[i]>>10);
        it b = x[i] - (a<<10);
        for (size_t j = 0; j < 1024; j++){
            it need = k[i] - __builtin_popcount(b&j);
            if (need >= 0 && need <= 10 && dp[a][j][need] + 1 > res[i])
                res[i] = dp[a][j][need] + 1, p[i] = pr[a][j][need];
        }
        for (size_t j = 0; j < 1024; j++){
            it cur = __builtin_popcount(a&j);
            if (dp[j][b][cur] < res[i])
                dp[j][b][cur] = res[i], pr[j][b][cur] = i;
        }
        if (res[i] > ans)
            ans = res[i], pos = i;
    }
    vector<it> path;
    while (pos){
        path.pb(pos);
        pos = p[pos];
    }
    reverse(path.begin(), path.end());
    cout << path.size() << endl;
    for (auto itt : path) cout << itt << ' ';
    return 0;
}

Compilation message (stderr)

subsequence.cpp:21:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:38:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (size_t i = 1; i <= n; i++){
                        ~~^~~~
subsequence.cpp:29:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("subsequence.in","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("subsequence.out","w",stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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