Submission #651825

#	Time	Username	Problem	Language	Result	Execution time	Memory
651825		ymm	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2649 ms	3304 KiB

subsequence

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
int dp[N], pre[N];
int a[N], k[N];
int n;

int get(int l, int r, int x, int k);
/*{
	#define MAX(a, b) ((a)>(b)?(a):(b))
	int ans = 0;
	Loop (j,l,r) {
		int tmp = a[j] & x;
		tmp =__builtin_popcount(tmp);
		tmp = -(tmp == k);
		tmp &= dp[j];
		ans = MAX(ans, tmp);
	}
	return ans;
	#undef MAX
}*/

asm("\n"
"	.section	.rodata.cst32,\"aM\",@progbits,32\n"
"	.p2align	5                               # -- Begin function _Z3getiiii\n"
".myLCPI0_0:\n"
"	.zero	32,15\n"
".myLCPI0_1:\n"
"	.byte	0                               # 0x0\n"
"	.byte	1                               # 0x1\n"
"	.byte	1                               # 0x1\n"
"	.byte	2                               # 0x2\n"
"	.byte	1                               # 0x1\n"
"	.byte	2                               # 0x2\n"
"	.byte	2                               # 0x2\n"
"	.byte	3                               # 0x3\n"
"	.byte	1                               # 0x1\n"
"	.byte	2                               # 0x2\n"
"	.byte	2                               # 0x2\n"
"	.byte	3                               # 0x3\n"
"	.byte	2                               # 0x2\n"
"	.byte	3                               # 0x3\n"
"	.byte	3                               # 0x3\n"
"	.byte	4                               # 0x4\n"
"	.byte	0                               # 0x0\n"
"	.byte	1                               # 0x1\n"
"	.byte	1                               # 0x1\n"
"	.byte	2                               # 0x2\n"
"	.byte	1                               # 0x1\n"
"	.byte	2                               # 0x2\n"
"	.byte	2                               # 0x2\n"
"	.byte	3                               # 0x3\n"
"	.byte	1                               # 0x1\n"
"	.byte	2                               # 0x2\n"
"	.byte	2                               # 0x2\n"
"	.byte	3                               # 0x3\n"
"	.byte	2                               # 0x2\n"
"	.byte	3                               # 0x3\n"
"	.byte	3                               # 0x3\n"
"	.byte	4                               # 0x4\n"
"	.text\n"
"	.globl	_Z3getiiii\n"
"	.p2align	4, 0x90\n"
"	.type	_Z3getiiii,@function\n"
"_Z3getiiii:                             # @_Z3getiiii\n"
"	.cfi_startproc\n"
"# %bb.0:\n"
"	pushq	%rbp\n"
"	.cfi_def_cfa_offset 16\n"
"	pushq	%rbx\n"
"	.cfi_def_cfa_offset 24\n"
"	.cfi_offset %rbx, -24\n"
"	.cfi_offset %rbp, -16\n"
"	xorl	%eax, %eax\n"
"	cmpl	%esi, %edi\n"
"	jge	.myLBB0_10\n"
"# %bb.1:\n"
"	movslq	%esi, %r10\n"
"	movslq	%edi, %rsi\n"
"	movq	%r10, %r8\n"
"	subq	%rsi, %r8\n"
"	xorl	%eax, %eax\n"
"	cmpq	$32, %r8\n"
"	jae	.myLBB0_3\n"
"# %bb.2:\n"
"	movq	%rsi, %r11\n"
"	jmp	.myLBB0_6\n"
".myLBB0_3:\n"
"	movq	%r8, %r9\n"
"	andq	$-32, %r9\n"
"	leaq	(%r9,%rsi), %r11\n"
"	vmovd	%edx, %xmm0\n"
"	vpbroadcastd	%xmm0, %ymm0\n"
"	vmovd	%ecx, %xmm1\n"
"	vpbroadcastd	%xmm1, %ymm1\n"
"	leaq	a(%rip), %rax\n"
"	leaq	96(%rax,%rsi,4), %rax\n"
"	leaq	dp(%rip), %rdi\n"
"	leaq	(%rdi,%rsi,4), %rsi\n"
"	addq	$96, %rsi\n"
"	vpxor	%xmm2, %xmm2, %xmm2\n"
"	xorl	%edi, %edi\n"
"	vmovdqa	.myLCPI0_0(%rip), %ymm3           # ymm3 = [15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15]\n"
"	vmovdqa	.myLCPI0_1(%rip), %ymm4           # ymm4 = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]\n"
"	vpxor	%xmm5, %xmm5, %xmm5\n"
"	vpxor	%xmm6, %xmm6, %xmm6\n"
"	vpxor	%xmm7, %xmm7, %xmm7\n"
"	vpxor	%xmm8, %xmm8, %xmm8\n"
"	.p2align	4, 0x90\n"
".myLBB0_4:                                # =>This Inner Loop Header: Depth=1\n"
"	vpand	-96(%rax,%rdi,4), %ymm0, %ymm10\n"
"	vpand	-64(%rax,%rdi,4), %ymm0, %ymm11\n"
"	vpand	-32(%rax,%rdi,4), %ymm0, %ymm12\n"
"	vpand	(%rax,%rdi,4), %ymm0, %ymm9\n"
"	vpand	%ymm3, %ymm10, %ymm13\n"
"	vpshufb	%ymm13, %ymm4, %ymm13\n"
"	vpsrlw	$4, %ymm10, %ymm10\n"
"	vpand	%ymm3, %ymm10, %ymm10\n"
"	vpshufb	%ymm10, %ymm4, %ymm10\n"
"	vpaddb	%ymm13, %ymm10, %ymm10\n"
"	vpunpckhdq	%ymm2, %ymm10, %ymm13   # ymm13 = ymm10[2],ymm2[2],ymm10[3],ymm2[3],ymm10[6],ymm2[6],ymm10[7],ymm2[7]\n"
"	vpsadbw	%ymm2, %ymm13, %ymm13\n"
"	vpunpckldq	%ymm2, %ymm10, %ymm10   # ymm10 = ymm10[0],ymm2[0],ymm10[1],ymm2[1],ymm10[4],ymm2[4],ymm10[5],ymm2[5]\n"
"	vpsadbw	%ymm2, %ymm10, %ymm10\n"
"	vpackuswb	%ymm13, %ymm10, %ymm10\n"
"	vpand	%ymm3, %ymm11, %ymm13\n"
"	vpshufb	%ymm13, %ymm4, %ymm13\n"
"	vpsrlw	$4, %ymm11, %ymm11\n"
"	vpand	%ymm3, %ymm11, %ymm11\n"
"	vpshufb	%ymm11, %ymm4, %ymm11\n"
"	vpaddb	%ymm13, %ymm11, %ymm11\n"
"	vpunpckhdq	%ymm2, %ymm11, %ymm13   # ymm13 = ymm11[2],ymm2[2],ymm11[3],ymm2[3],ymm11[6],ymm2[6],ymm11[7],ymm2[7]\n"
"	vpsadbw	%ymm2, %ymm13, %ymm13\n"
"	vpunpckldq	%ymm2, %ymm11, %ymm11   # ymm11 = ymm11[0],ymm2[0],ymm11[1],ymm2[1],ymm11[4],ymm2[4],ymm11[5],ymm2[5]\n"
"	vpsadbw	%ymm2, %ymm11, %ymm11\n"
"	vpackuswb	%ymm13, %ymm11, %ymm11\n"
"	vpand	%ymm3, %ymm12, %ymm13\n"
"	vpshufb	%ymm13, %ymm4, %ymm13\n"
"	vpsrlw	$4, %ymm12, %ymm12\n"
"	vpand	%ymm3, %ymm12, %ymm12\n"
"	vpshufb	%ymm12, %ymm4, %ymm12\n"
"	vpaddb	%ymm13, %ymm12, %ymm12\n"
"	vpunpckhdq	%ymm2, %ymm12, %ymm13   # ymm13 = ymm12[2],ymm2[2],ymm12[3],ymm2[3],ymm12[6],ymm2[6],ymm12[7],ymm2[7]\n"
"	vpsadbw	%ymm2, %ymm13, %ymm13\n"
"	vpunpckldq	%ymm2, %ymm12, %ymm12   # ymm12 = ymm12[0],ymm2[0],ymm12[1],ymm2[1],ymm12[4],ymm2[4],ymm12[5],ymm2[5]\n"
"	vpsadbw	%ymm2, %ymm12, %ymm12\n"
"	vpackuswb	%ymm13, %ymm12, %ymm12\n"
"	vpand	%ymm3, %ymm9, %ymm13\n"
"	vpshufb	%ymm13, %ymm4, %ymm13\n"
"	vpsrlw	$4, %ymm9, %ymm9\n"
"	vpand	%ymm3, %ymm9, %ymm9\n"
"	vpshufb	%ymm9, %ymm4, %ymm9\n"
"	vpaddb	%ymm13, %ymm9, %ymm9\n"
"	vpunpckhdq	%ymm2, %ymm9, %ymm13    # ymm13 = ymm9[2],ymm2[2],ymm9[3],ymm2[3],ymm9[6],ymm2[6],ymm9[7],ymm2[7]\n"
"	vpsadbw	%ymm2, %ymm13, %ymm13\n"
"	vpunpckldq	%ymm2, %ymm9, %ymm9     # ymm9 = ymm9[0],ymm2[0],ymm9[1],ymm2[1],ymm9[4],ymm2[4],ymm9[5],ymm2[5]\n"
"	vpsadbw	%ymm2, %ymm9, %ymm9\n"
"	vpackuswb	%ymm13, %ymm9, %ymm9\n"
"	vpcmpeqd	%ymm1, %ymm10, %ymm10\n"
"	vpcmpeqd	%ymm1, %ymm11, %ymm11\n"
"	vpcmpeqd	%ymm1, %ymm12, %ymm12\n"
"	vpcmpeqd	%ymm1, %ymm9, %ymm9\n"
"	vpand	-96(%rsi,%rdi,4), %ymm10, %ymm10\n"
"	vpmaxsd	%ymm10, %ymm5, %ymm5\n"
"	vpand	-64(%rsi,%rdi,4), %ymm11, %ymm10\n"
"	vpmaxsd	%ymm10, %ymm6, %ymm6\n"
"	vpand	-32(%rsi,%rdi,4), %ymm12, %ymm10\n"
"	vpand	(%rsi,%rdi,4), %ymm9, %ymm9\n"
"	vpmaxsd	%ymm10, %ymm7, %ymm7\n"
"	vpmaxsd	%ymm9, %ymm8, %ymm8\n"
"	addq	$32, %rdi\n"
"	cmpq	%rdi, %r9\n"
"	jne	.myLBB0_4\n"
"# %bb.5:\n"
"	vpmaxsd	%ymm6, %ymm5, %ymm0\n"
"	vpmaxsd	%ymm7, %ymm0, %ymm0\n"
"	vpmaxsd	%ymm8, %ymm0, %ymm0\n"
"	vextracti128	$1, %ymm0, %xmm1\n"
"	vpmaxsd	%xmm1, %xmm0, %xmm0\n"
"	vpshufd	$238, %xmm0, %xmm1              # xmm1 = xmm0[2,3,2,3]\n"
"	vpmaxsd	%xmm1, %xmm0, %xmm0\n"
"	vpshufd	$85, %xmm0, %xmm1               # xmm1 = xmm0[1,1,1,1]\n"
"	vpmaxsd	%xmm1, %xmm0, %xmm0\n"
"	vmovd	%xmm0, %eax\n"
"	cmpq	%r9, %r8\n"
"	jne	.myLBB0_6\n"
".myLBB0_10:\n"
"	popq	%rbx\n"
"	.cfi_def_cfa_offset 16\n"
"	popq	%rbp\n"
"	.cfi_def_cfa_offset 8\n"
"	vzeroupper\n"
"	retq\n"
".myLBB0_6:\n"
"	.cfi_def_cfa_offset 24\n"
"	subq	%r11, %r10\n"
"	shlq	$2, %r11\n"
"	xorl	%esi, %esi\n"
"	leaq	a(%rip), %r9\n"
"	leaq	dp(%rip), %r8\n"
"	movl	%eax, %edi\n"
"	jmp	.myLBB0_7\n"
"	.p2align	4, 0x90\n"
".myLBB0_9:                                #   in Loop: Header=BB0_7 Depth=1\n"
"	cmpl	%eax, %edi\n"
"	cmovgl	%edi, %eax\n"
"	incq	%rsi\n"
"	movl	%eax, %edi\n"
"	cmpq	%rsi, %r10\n"
"	je	.myLBB0_10\n"
".myLBB0_7:                                # =>This Inner Loop Header: Depth=1\n"
"	leaq	(%r11,%rsi,4), %rbx\n"
"	movl	(%r9,%rbx), %eax\n"
"	andl	%edx, %eax\n"
"	popcntl	%eax, %ebp\n"
"	movl	$0, %eax\n"
"	cmpl	%ecx, %ebp\n"
"	jne	.myLBB0_9\n"
"# %bb.8:                                #   in Loop: Header=BB0_7 Depth=1\n"
"	movl	(%r8,%rbx), %eax\n"
"	jmp	.myLBB0_9\n"
".myLfunc_end0:\n"
"	.size	_Z3getiiii, .myLfunc_end0-_Z3getiiii\n"
"	.cfi_endproc\n"
);

void up(int i, int x, int k)
{
	int ans = 0, ansi = -1;
	const int S = 4096;
	for (int l = 0; l < i; l += S) {
		int r = min(l+S, i);
		int tmp = get(l, r, x, k);
		if (tmp > ans) {
			ans = tmp;
			ansi = l;
		}
	}
	if (ansi >= 0) {
		Loop (j,ansi,ansi+S) {
			if (  dp[j] == ans
			    && __builtin_popcount(a[j]&x) == k) {
				ansi = j;
				break;
			}
		}
	}
	pre[i] = ansi;
	dp[i] = ans+1;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n)
		cin >> a[i];
	Loop (i,0,n)
		cin >> k[i];
	Loop (i,0,n)
		up(i, a[i], k[i]);
	int i = 0;
	Loop (j,0,n) {
		if (dp[j] > dp[i])
			i = j;
	}
	vector<int> vec;
	while (i != -1) {
		vec.push_back(i);
		i = pre[i];
	}
	reverse(vec.begin(), vec.end());
	cout << vec.size() << '\n';
	for (int v : vec)
		cout << v+1 << ' ';
	cout << '\n';
}

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