Submission #42402

#	Time	Username	Problem	Language	Result	Execution time	Memory
42402		Aidyn_A	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3899 ms	136728 KiB

subsequence

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#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)1e5 + 123;
const ll INF = (ll)1e18 + 123;
const int inf = (int)1e9 + 123;
const int MOD = (int)1e9 + 7;

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() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) 
		scanf("%d", &a[i]);
	for(int i = 1; i <= n; i ++) 
		scanf("%d", &b[i]);
	int res = -1, res_p = -1;
	for(int i = 1; i <= n; i ++) {
	  now[i] = 1;
		//GET
		int j = 0, origin = (a[i] >> half), firsthalf = (a[i] >> half);
		for(int mask = 0; mask < (1 << half); mask ++) {
			int left = b[i] - __builtin_popcount(origin & mask);
			if(left >= 0 && left <= 10) {
				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;
		for(int mask = 0; mask < (1 << half); mask ++) {
			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);
	vector<int> v;
	while(res_p > 0) {
		v.pb(res_p);
		res_p = pr[res_p];		
	}
	for(int i = sz(v) - 1; i >= 0; i --)
		printf("%d ", v[i]);
	return 0;  
}

Compilation message (stderr)

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

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