Submission #1178090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178090		sitingfake	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	3949 ms	165848 KiB

subsequence

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

// define

#define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s";
#define ll long long
#define ld long double
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) ((x>>(i))&1LL)
#define flip(x,i) (x^(1LL<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define INF 0x3f
#define sitingfake 1
#define orz 1
#define task ""

//constant

const ll mod=1e9+7;
const long long linf=4557430888798830399;
const int inf=1061109567;
const int maxarr=1e6+5;
const double pi=acos(-1);
const int dx[]={0,1,-1,0};
const int dy[]={1,0,0,-1};

// template function

template<typename T> bool maximize(T &a, const T &b)
{
    if(a<b)
    {
        a=b;
        return 1;
    }
    return 0;
}

template<typename T> bool minimize(T &a, const T &b)
{
    if(a>b)
    {
        a=b;
        return 1;
    }
    return 0;
}

//code
const int maxn = 1e5 + 7;

int bitcnt[maxn], a[maxn];

int n ;

ii dp[1<<10][1<<10][20];

int trace[maxn];

int ans = 1, pos = 1;
// dp i j k thg pre co bit trai la i, and thg j va co bit phai la k


void solve()
{
	cin >> n;

	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}

	for(int i = 1;i <= n ;i++)
	{
		cin >> bitcnt[i];
	}

	for(int i = 1; i<=n ;i++)
	{
		int LeftBit = a[i] & ((1<<10) - 1);
		int RightBit = a[i] >> 10;
		int res = 1, P = 0;
		for(int mask = 0 ; mask <(1<<10); mask ++)
		{
			int cnt = __builtin_popcount(mask & LeftBit);
			if(cnt > bitcnt[i]) continue;
			int need = bitcnt[i] - cnt;
			if(need > 10) continue;

			if(dp[mask][RightBit][need].fi + 1 > res)
			{
				res = dp[mask][RightBit][need].fi + 1;
				P = dp[mask][RightBit][need].se;
			}
		}

		trace[i] = P;

		if(res > ans)
		{
			ans = res; 
			pos = i;
		}

		for(int mask = 0; mask < (1<<10); mask ++)
		{
			int k =__builtin_popcount(RightBit & mask);
			if(dp[LeftBit][mask][k].fi < res)
			{
				dp[LeftBit][mask][k].fi = res;
				dp[LeftBit][mask][k].se = i;
			}
		}
	}

	vector<int>res;
	while(trace[pos] != 0)
	{
		res.push_back(pos);
		pos = trace[pos];
	}
	res.push_back(pos);

	reverse(all(res));

	cout << ans << "\n";

	for(int i : res) cout << i << " ";
}


signed main()
{
	   ios_base::sync_with_stdio(0);
	   cin.tie(0);
	   cout.tie(0);

	   if(fopen(task".inp","r"))
	   {
	       freopen(task".inp","r",stdin);
	       freopen(task".out","w",stdout);
	   }

	   int tc; tc=1;

	   while(tc--) {solve();}
}
/*
                                 ..
                        .:^!7?JJJYJJJJ?77!!~^.
                   .:~7JYYJYYJJ?77?J??JY?JYY5YY?7~:.
                 :!J5YJ??777J?J?????7J?J?7J?J?JYYYYY?~.
               :?5JJ???77!?77?J??J7?7???JJJJ?J777??JYJY?!.
             ^J5YYJJJ77?!7!7!77JJJJ?J77??Y???77!!777!7?JY5?^
           ~JYY??J7??7J?7?!7!7???J?77!777J?JY?J7777?7?????5PY^
         ^Y5J??J??!!???J??77777????J?J77?YY?!~^::::::^!77??YPG7.
        !PY?777?77!7!7J?7!7?????JJ??7J??J^:.           .:!7?75GY:
      .JPJ!7!7?7?7!7!????????J?7??7J?YJ~.                .:!7?JGP^
     .JP?!7!!??7J7!!!?7J????7J7!!?!?7?7.                 .  ^??YG5:
     !P??7777?77??777?7?!7!777!?7J??J?^              :~~:  . ^?7YGY.
    :PY7??77!7~~:::.....:^^~!7??????J?^        .   .7PGGPY: . !?JPB~
   .Y5!!Y77!~:..            .:~7JJJ??J!.       . . .5GGGGP^ ..:J?JBJ
   ~G?!!?7!^.                  .^7JJYYJ7:.      . ..:~???~^^:..77?G5.
   !G!7?77:                     ..?J7~^~!77: .  .. ..^~~~~~~~:.!75B!
   !P77J7^                     ..~?:::^~!7?^ ........^~^^^^^:.^JYG?.
   !G???!:      .~77!:.        ..7?7?77~:....................^JPJ~
   :P5??7:     .JGGGGP!        ......  ..................:^!JP?^
    7BJ7J~     .JGGGGG~       . .....................::::^!7?JJ?!^.
    .YG?Y7^     .~7??~:::.     ..  .... ... ....::::::::::::^?~^!?J7:
     :PPJ??:    ..:^^^^^^:     .  .... ....::::^::::::::.:::^JP~..:75~
      :YGYJ?^.  .^^^^^^^:.        .....:::::::::::...:::..:.::JP!~~7Y~
        ~PP5J?^...::::.... ......::::::::.:.::.:::::.:::::::::^JP?7~.
         :75P5YJ!~^^^^!:...::^:::::::...:......::.....::::::::^^5?
           ?G?Y55PP5YJ!^:::::::::..:..:.:....:...:....::..::::^^7G^
           ~P!^:::::.::::::::::::::...:.::::.:.:::::.:.......:::^PY
            :!JJ7~^::::::::::::::::..:.:.::.:::::...::.........:.JP.
               :5P?^:^:::::^::::::::::::.::::::.:.::.::........::7P:
               .P7::::::::::^::^^::::::::::::::::.:.........:::::J5.
           .   ^G~:^^:::::::^:^^^^^:::::::::^:::::::::::::::^^::75^
               :P!^^^^^^^^:^^^^^^:^:::::^:::^:::::::::::::::^^7JY^
               .!5~^~^^^^^^^^^:^^^^^^^^:^^^^:^^^^^^^^^^^^^^~?55G?
                 ~J?~~~^^~~^~~~^^^^^^^:^^^~^^^^^^^^~~!!!?Y55GP?J!.
                  .~PYJ?77?7777!!!!!!!!!!!!7777??JJJJJ5PP5??J^  ..
                   .777?5J??YYYYY5?7777!!!!~!~~^^::.  .::
                        :!!~:.:^^:

        <(")
*/

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:145:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |                freopen(task".inp","r",stdin);
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:146:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |                freopen(task".out","w",stdout);
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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