Submission #42396

#	Time	Username	Problem	Language	Result	Execution time	Memory
42396		Aidyn_A	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	11 ms	1984 KiB

subsequence

#include <stdio.h>
#include <bits/stdc++.h>			

#define pb push_back
#define pf push_front
#define pp pop_back
#define sz(a) (int)(a.size())
#define mp make_pair
#define F first
#define S second
#define next _next
#define prev _prev
#define left _left
#define right _right
#define y1 _y1
#define all(x) x.begin(), x.end()
#define what_is(x) #x << " is " << (x)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = (int)1e6 + 123;
const ll INF = (ll)1e18 + 123;
const int inf = (int)1e9 + 123;
const int MOD = (int)1e9 + 7;

void megaRandom() {
	unsigned int FOR;
 	asm("rdtsc" : "=A"(FOR));
  srand(FOR);
}

int n, a[N], b[N];
int half = 10;
pii dp[(1<<10) + 123][(1<<10) + 123][11];
int now[N], pr[N];

int main() {
	megaRandom();
	scanf("%d", &n);//cin >> n;
	for(int i = 1; i <= n; i ++) 
		scanf("%d", &a[i]);//cin >> a[i];
	for(int i = 1; i <= n; i ++) 
		scanf("%d", &b[i]);//cin >> b[i];
	int res = 0, res_p = -1;
	for(int i = 1; i <= n; i ++) {
		//GET
		int j = -1;
		for(int mask = 0; mask < (1 << half); mask ++) {
			int origin = (mask << half);
			int left = b[i] - __builtin_popcount(origin & a[i]);
			if(left >= 0) {
				int lasthalf = (a[i] & ((1 << half) - 1));
				if(dp[mask][lasthalf][left].F + 1 > now[i]) {
					now[i] = dp[mask][lasthalf][left].F + 1;				
					j = dp[mask][lasthalf][left].S;  
				}
			}
		}
		pr[i] = j;
		if(j > 0) {
			//cout << "i: " << i << " j: " << j << "\n";
			
			assert(__builtin_popcount(a[i] & a[j]) == b[i]);
		}
		//cout << "i: " << i << " now: " << now[i] << "\n";   
		//UPDATE
		for(int mask = 0; mask < (1 << half); mask ++) {
			int firsthalf = (a[i] >> half);
			int changed = __builtin_popcount(a[i] & mask);
			if(dp[firsthalf][mask][changed].F < now[i]) {
				dp[firsthalf][mask][changed] = {now[i], i};
			}
		}
		if(now[i] > res)
			res = now[i], res_p = i;
	}
	printf("%d\n", res);//cout << res << "\n";           
	vector<int> v;
	while(res_p > 0) {
		v.pb(res_p);
		res_p = pr[res_p];		
	}
	reverse(all(v));
	for(auto aa : v)
		printf("%d ", aa);//cout << aa << ' ';
	return 0;  
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:45:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);//cin >> n;
                 ^
subsequence.cpp:47:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);//cin >> a[i];
                     ^
subsequence.cpp:49:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &b[i]);//cin >> b[i];
                     ^

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