Submission #1316863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316863		thuhienne	Longest beautiful sequence (IZhO17_subsequence)	C++20	Compilation error	0 ms	0 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define re exit(0);

#define fi first
#define se second

const int maxx = 1023;
const int maxn = 100009;
const int LOG = 20;

int n,arr[maxn],num[maxn];

int popcount[maxx + 9][maxx + 9];

pair <int,int> maxvalue[maxx + 9][maxx + 9][LOG + 1];
pair <int,int> dp[maxn];

void update(pair <int,int>& a,pair <int,int> b) {
	if (b.first > a.first) a = b;
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);

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

	for (int i = 0;i <= maxx;i++) {
		for (int j = 0;j <= maxx;j++) {
			popcount[i][j] = __builtin_popcount(i & j);
			
			for (int k = 0;k <= LOG;k++) maxvalue[i][j][k] = {0,-1};
		
		}
	}
	
	int res = 0;
	
	for (int i = 1;i <= n;i++) {
		dp[i].fi = 1;
		
		int first = arr[i] & maxx;
		int second = arr[i] >> 10;
		
		for (int j = 0;j <= maxx;j++) {
			int need = num[i] - popcount[first][j];
			
			if (need >= 0) {
				pair <int,int> temp = maxvalue[j][second][need];
				update(dp[i],{temp.fi + 1,temp.se});
			}
		}
		
		for (int j = 0;j <= maxx;j++) {
			update(maxvalue[first][j][popcount[second][j]],{dp[i].fi,i});
		}
		
		res = max(res,dp[i].fi);
	}
	
	int last;
	for (int i = 1;i <= n;i++) if (dp[i].fi == res) {
		last = i;
		break;
	}
	
	cout << res << '\n';
	
	vector <int> tmp;
	while (res--) {
		tmp.push_back(last);
		last = dp[last].se;
	}
	
	while (tmp.size()) {
		cout << tmp.back() << " ";
		tmp.pop_back();
	}

}

/*
Aiming:
                                                           ==
                                                         +++++***
                                                        +:::::-=*
                                                         ------=
         ==========           ==================         --:--==              ============--
         ==========           ==-------=--:=--====       ---==++           ===========--====-=
        ==--========          ==--=================      =:::-=+          ==============----====
        ==:-=========         ===:===       =======      =::--=+         ========        ==--====
       ==--==========         ==-:===        =======     -:::-:=        =======           =======
      ==--:==  =======        ==--===        =======     =-:::-=        =======            =======
      =-.-===   =======       ==-====       =======     *:::----*       =======            =======
     ==--:==    =======       ==-==================     +-:::::-+       ======             =======
    ==-:-===     =======      ==--================     *=-:::::-=       =======            =======
    ==---===============      ==--=============        +--::---==*      ====--=            =======
   ===--=================     ==:-===                  =:-::::--=+      ====-===          =======
   ==.-===================    ==--===                  =::::::---+       ====---==      =========
  ==---==          =======    =======                 +-:---=====+        ==-===--==============
 =======            =======   =======                 =-:::::::--=+         =--=-=============
========             =======  =======                 =--::::::--=+           =============
                                                   ***++++++++++*****
*/

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:35:25: error: reference to 'popcount' is ambiguous
   35 |                         popcount[i][j] = __builtin_popcount(i & j);
      |                         ^~~~~~~~
In file included from /usr/include/c++/13/bits/stl_algobase.h:76,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from subsequence.cpp:1:
/usr/include/c++/13/bit:426:5: note: candidates are: 'template<class _Tp> constexpr std::_If_is_unsigned_integer<_Tp, int> std::popcount(_Tp)'
  426 |     popcount(_Tp __x) noexcept
      |     ^~~~~~~~
subsequence.cpp:17:5: note:                 'int popcount [1032][1032]'
   17 | int popcount[maxx + 9][maxx + 9];
      |     ^~~~~~~~
subsequence.cpp:51:45: error: reference to 'popcount' is ambiguous
   51 |                         int need = num[i] - popcount[first][j];
      |                                             ^~~~~~~~
/usr/include/c++/13/bit:426:5: note: candidates are: 'template<class _Tp> constexpr std::_If_is_unsigned_integer<_Tp, int> std::popcount(_Tp)'
  426 |     popcount(_Tp __x) noexcept
      |     ^~~~~~~~
subsequence.cpp:17:5: note:                 'int popcount [1032][1032]'
   17 | int popcount[maxx + 9][maxx + 9];
      |     ^~~~~~~~
subsequence.cpp:60:51: error: reference to 'popcount' is ambiguous
   60 |                         update(maxvalue[first][j][popcount[second][j]],{dp[i].fi,i});
      |                                                   ^~~~~~~~
/usr/include/c++/13/bit:426:5: note: candidates are: 'template<class _Tp> constexpr std::_If_is_unsigned_integer<_Tp, int> std::popcount(_Tp)'
  426 |     popcount(_Tp __x) noexcept
      |     ^~~~~~~~
subsequence.cpp:17:5: note:                 'int popcount [1032][1032]'
   17 | int popcount[maxx + 9][maxx + 9];
      |     ^~~~~~~~