Submission #337982

#	Time	Username	Problem	Language	Result	Execution time	Memory
337982		boykut	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	929 ms	3948 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

#define all(a) a.begin(),a.end()

signed main() {
   ios::sync_with_stdio(0);
   cin.tie(0);
   int n;
   cin >> n;
   vector <int> a(n);
   vector <int> k(n);
   for (int i = 0; i < n; i++) {
      cin >> a[i];
   }
   for (int i = 0; i < n; i++) {
      cin >> k[i];
   }
   if (n <= 15) {
      int ans = 0, ans_size = 0;
      for (int i = 0; i < (1 << n); i++) {
         int num = i, index = n - 1;
         vector <int> j;
         while (num) {
            if (num & 1)
               j.push_back(index);
            index--;
            num >>= 1;
         }
         reverse(j.begin(), j.end());
         int ok = true;
         for (int l = 1; l < j.size(); l++) {
            if (__builtin_popcount(a[j[l]] & a[j[l - 1]]) != k[j[l]]) 
               ok = false;
         }
         if (ok) {
            if (j.size() >= ans_size) {
               ans_size = j.size();
               ans = i;
            }
         }
      }
      int num = ans, index = n - 1;
      vector <int> j;
      while (num) {
         if (num & 1)
            j.push_back(index);
         index--;
         num >>= 1;
      }
      reverse(j.begin(), j.end());
      cout << j.size() << '\n';
      for (int i = 0; i < j.size(); i++) {
         cout << j[i] + 1 << ' ';
      }
   } else if (n <= 5000) {
      vector <int> dp(n, 1);
      vector <int> p(n, -1);
      
      auto can = [&](int l, int r) -> bool{
         return (__builtin_popcount(a[r] & a[l]) == k[r]);
      };
      
      int index = 0;
      
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < i; j++) {
            if (can(j, i) && dp[j] + 1 > dp[i]) {
               dp[i] = dp[j] + 1;
               p[i] = j;
            }
         }
         if (dp[i] >= dp[index]) {
            index = i;
         }
      }
      int v = index;
      vector <int> ans;
      while (v != -1) {
         ans.push_back(v);
         v = p[v];
      }
      reverse(all(ans));
      cout << ans.size() << '\n';
      for (int i = 0; i < ans.size(); i++)
         cout << ans[i]+1 << ' ';
   } else {
      vector <int> dp(n, 1);
      vector <int> p(n, -1);
      vector <int> inds[1 << 10];
      
      for (int i = 0; i < n; i++) {
         inds[a[i]].push_back(i);
      }
      
      auto can = [&](int l, int r, int k) -> bool{
         return (__builtin_popcount(l & r) == k);
      };
      
      int index = 0;
      
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < (1 << 10); j++) {
            if (can(a[i], j, k[i])) {
               for (auto indexs : inds[j]) {
                  if (indexs >= i) break;
                  if (dp[i] < dp[indexs] + 1) {
                     dp[i] = dp[indexs] + 1;
                     p[i] = indexs;
                  }
               }
            }
         }
         if (dp[i] >= dp[index]) {
            index = i;
         }
      }
      
      int v = index;
      vector <int> ans;
      while (v != -1) {
         ans.push_back(v);
         v = p[v];
      }
      reverse(all(ans));
      
      cout << ans.size() << '\n';
      for (int i = 0; i < ans.size(); i++)
         cout << ans[i]+1 << ' ';
      cout << '\n';
   }
   return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:33:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |          for (int l = 1; l < j.size(); l++) {
      |                          ~~^~~~~~~~~~
subsequence.cpp:38:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |             if (j.size() >= ans_size) {
      |                 ~~~~~~~~~^~~~~~~~~~~
subsequence.cpp:54:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |       for (int i = 0; i < j.size(); i++) {
      |                       ~~^~~~~~~~~~
subsequence.cpp:86:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |       for (int i = 0; i < ans.size(); i++)
      |                       ~~^~~~~~~~~~~~
subsequence.cpp:129:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |       for (int i = 0; i < ans.size(); i++)
      |                       ~~^~~~~~~~~~~~

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