Submission #38268

#	Time	Username	Problem	Language	Result	Execution time	Memory
38268		mirbek01	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	169 ms	4108 KiB

subsequence

# include <bits/stdc++.h>

# define pb push_back
# define fr first
# define sc second
# define mk make_pair

using namespace std;

const long long linf = 1e18 + 7;
const int inf = 1e9 + 7;
const int N = 1e5 + 5;

typedef long long ll;

int n, m, a[N], k[N], dp[N], p[N], ot[N];
vector <int> ans;

int main(){
      cin >> n;

      for(int i = 1; i <= n; i ++){
            cin >> a[i];
            dp[i] = 1;
            ot[i] = i;
            m = max(m, a[i]);
      }

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

      int pos = 0, mx = -1;

      for(int i = 1; i <= n; i ++)
      {
            if(m <= (1 << 8)){
                  for(int q = 0; q <= (1 << 8); q ++){
                        int j = p[q];
                        int bit = __builtin_popcount(a[i] & a[j]);
                        if(bit == k[i] && j)
                        {
                              if(dp[i] <= dp[j])
                              {
                                    dp[i] = dp[j] + 1;
                                    ot[i] = j;
                              }
                        }
                  }
                  p[a[i]] = i;
            } else
            for(int j = i - 1; j >= 1; j --){
                  int bit = __builtin_popcount(a[i] & a[j]);
                  if(bit == k[i]){
                        if(dp[i] <= dp[j]){
                              dp[i] = dp[j] + 1;
                              ot[i] = j;
                        }
                  }
            }

            if(mx < dp[i])
            {
                  mx = dp[i];
                  pos = i;
            }
      }

      mx = pos;

      while(1)
      {
            ans.pb(pos);
            pos = ot[pos];
            if(ans.size() >= dp[mx]) break;
      }

      cout << ans.size() << endl;
      reverse(ans.begin(), ans.end());
      for(int i : ans)
            cout << i << " ";
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:74:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(ans.size() >= dp[mx]) break;
                           ^

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