Submission #38266

#	Time	Username	Problem	Language	Result	Execution time	Memory
38266		mirbek01	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	173 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, 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;
      }

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

      if(n <= 5000){
            int pos = 0, mx = -1;

            for(int i = 1; i <= n; i ++)
            {
                  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;
            }
      } else {
            int pos = 0, mx = -1;
            for(int i = 1; i <= n; i ++){
                  for(int j = 0; j < 256; j ++)
                  {
                        int bit = __builtin_popcount(j & a[i]), d = p[j];
                        if(bit == k[i] && p)
                        {
                              if(dp[i] <= dp[d])
                              {
                                    dp[i] = dp[d] + 1;
                                    ot[i] = d;
                              }
                        }
                  }
                  p[a[i]] = i;
                  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:62:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   if(ans.size() >= dp[mx]) break;
                                 ^
subsequence.cpp:70:43: warning: the address of 'p' will always evaluate as 'true' [-Waddress]
                         if(bit == k[i] && p)
                                           ^
subsequence.cpp:92:33: 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