Submission #337918

#	Time	Username	Problem	Language	Result	Execution time	Memory
337918		boykut	Longest beautiful sequence (IZhO17_subsequence)	C++14	7 / 100	8 ms	384 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

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 << ' ';
      }
   }
   return 0;
}

Compilation message (stderr)

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

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