CSES - Datatähti 2021 alku - Results
Submission details
Task:Alitaulukot
Sender:hltk
Submission time:2020-10-02 23:46:15 +0300
Language:Assembly
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED11
#2ACCEPTED26
#3ACCEPTED63
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3details
#2ACCEPTED0.00 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.00 s1, 2, 3details
#5ACCEPTED0.00 s1, 2, 3details
#6ACCEPTED0.01 s2, 3details
#7ACCEPTED0.01 s2, 3details
#8ACCEPTED0.00 s2, 3details
#9ACCEPTED0.01 s2, 3details
#10ACCEPTED0.00 s2, 3details
#11ACCEPTED0.03 s3details
#12ACCEPTED0.03 s3details
#13ACCEPTED0.03 s3details
#14ACCEPTED0.03 s3details
#15ACCEPTED0.03 s3details
#16ACCEPTED0.03 s3details
#17ACCEPTED0.03 s3details

Code

%macro r1_push 0 ; push registers except rax
	push rbx
	push rcx
	push rdx
	push r8
	push r9
	push r10
	push r11
%endmacro
%macro r1_pop 0 ; pop registers except rax
	pop r11
	pop r10
	pop r9
	pop r8
	pop rdx
	pop rcx
	pop rbx
%endmacro
%macro r_push 0 ; push registers including rax
	push rax
	r1_push
%endmacro
%macro r_pop 0 ; pop registers including rax
	r1_pop
	pop rax
%endmacro

%define IBUFSZ 1048576
%define OBUFSZ 100
%define L 17
%define P 131072

	section .bss
	ibuf resb IBUFSZ
	obuf resb OBUFSZ
	sprmin resq L * P
	sprmax resq L * P
	N resq 1
	K resq 1

	section .text
	global _start
_start:
	; read ibuf
	xor rax, rax
	xor rdi, rdi
	mov rsi, ibuf
	mov rdx, IBUFSZ
	syscall
 
	mov rsi, ibuf
	mov rdi, obuf

	call stoi
	mov r9, rax
	mov [N], rax
	call stoi
	mov [K], rax

	xor rcx, rcx
.s1:
	call stoi
	mov qword [sprmin + rcx * 8], rax
	mov qword [sprmax + rcx * 8], rax
	inc rcx
	cmp rcx, r9
	jl .s1
	cmp qword [N], 1
	je .s3
	mov r10, 1
	mov r11, 1
	mov r12, 2
.s2:
	mov r13, [N]
	inc r13
	sub r13, r12
	xor r14, r14
.s4:
	lea rax, [r10 - 1]
	imul rax, P
	mov rbx, rax
	add rax, r14
	mov rax, [sprmin + rax * 8]
	add rbx, r11
	add rbx, r14
	mov rbx, [sprmin + rbx * 8]
	cmp rbx, rax
	cmovbe rax, rbx
	mov rbx, r10
	imul rbx, P
	add rbx, r14
	mov [sprmin + rbx * 8], rax
	inc r14
	cmp r14, r13
	jl .s4
	shl r11, 1
	shl r12, 1
	inc r10
	cmp r12, [N]
	jle .s2
	mov r10, 1
	mov r11, 1
	mov r12, 2
.s5:
	mov r13, [N]
	inc r13
	sub r13, r12
	xor r14, r14
.s6:
	lea rax, [r10 - 1]
	imul rax, P
	mov rbx, rax
	add rax, r14
	mov rax, [sprmax + rax * 8]
	add rbx, r11
	add rbx, r14
	mov rbx, [sprmax + rbx * 8]
	cmp rax, rbx
	cmovbe rax, rbx
	mov rbx, r10
	imul rbx, P
	add rbx, r14
	mov [sprmax + rbx * 8], rax
	inc r14
	cmp r14, r13
	jl .s6
	shl r11, 1
	shl r12, 1
	inc r10
	cmp r12, [N]
	jle .s5
.s3:
	mov r10, [K]
	; r9 = n, r10 = k
	xor r11, r11
	xor r12, r12
.s7:
.s8:
	mov r13, r11
	sub r13, r12
	inc r13
	bsr r13, r13
	xor r13, 31
	mov r14, 31
	sub r14, r13
	mov rcx, r14
	mov r13, 1
	sal r13, cl
	imul r14, P
	; r14 = d
	; r13 = 1 << d
	mov rax, r14
	add rax, r12
	mov rax, [sprmax + rax * 8]
	mov rbx, r14
	add rbx, r11
	sub rbx, r13
	inc rbx
	mov rbx, [sprmax + rbx * 8]
	cmp rax, rbx
	cmovbe rax, rbx
	mov rbx, r14
	add rbx, r12
	mov rbx, [sprmin + rbx * 8]
	mov rcx, r14
	add rcx, r11
	sub rcx, r13
	inc rcx
	mov rcx, [sprmin + rcx * 8]
	cmp rcx, rbx
	cmovbe rbx, rcx
	sub rax, rbx
	cmp rax, r10
	jle .s9
	inc r12
	jmp .s8
.s9:
	mov rax, r11
	sub rax, r12
	inc rax
	add r15, rax
	inc r11
	cmp r11, r9
	jl .s7
	mov rax, r15
	call printi
	mov rax, 0xa
	stosb

	; output obuf
	sub rdi, obuf
	mov rdx, rdi
	mov rdi, 1
	mov rax, 1
	mov rsi, obuf
	syscall
	
	; exit syscall
	mov rax, 0x3c
	xor rdi, rdi
	syscall
 
stoi: ; reads in integer from rsi s buffer and outputs it to rax
	r1_push
	xor r8,r8
	mov r9, 1
.a_stoi:
	xor rax, rax
	lodsb
	cmp al, 45
	jne .b_stoi
	mov r9, -1
	jmp .a_stoi
.b_stoi:
	cmp al, 32
	je .c_stoi
 
	cmp al, 10
	je .c_stoi
 
	cmp al, 0
	je .c_stoi
 
	sub al, 48
	mov rdx, 10
	imul r8, rdx
	add r8, rax
	jmp .a_stoi
.c_stoi:
	mov rax, r8
	imul rax, r9
	r1_pop
	ret

printi: ; outputs an integer rdi s buffer
	push rax
	r1_push
	xor rbx, rbx
	cmp rax, 0
	jnl .a_printi
	imul rax, -1
	push rax
	mov rax, 45
	stosb
	pop rax
.a_printi:
	xor rdx, rdx
	mov rcx, 10
	idiv rcx
	add rdx, 48
	push rdx
	inc rbx
	cmp rax, 0
	jne .a_printi
	mov rcx, rbx
.b_printi:
	pop rax
	stosb
	loop .b_printi
	mov rax, rdi
	r1_pop
	mov rdi, rax
	pop rax
	ret

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
100 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
5050

user output
5050

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
100 2
5 5 2 4 3 5 3 4 3 2 3 4 5 4 4 ...

correct output
317

user output
317

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
100 10
71 60 61 96 25 10 10 9 84 85 1...

correct output
119

user output
119

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
100 990000000
111122929 961821360 578238211 ...

correct output
4006

user output
4006

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
100 1000000000
553190572 453407680 667300705 ...

correct output
5050

user output
5050

Test 6

Group: 2, 3

Verdict: ACCEPTED

input
2000 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
2001000

user output
2001000

Test 7

Group: 2, 3

Verdict: ACCEPTED

input
2000 2
4 4 1 4 2 3 1 2 1 3 5 2 2 4 4 ...

correct output
6340

user output
6340

Test 8

Group: 2, 3

Verdict: ACCEPTED

input
2000 10
65 88 33 88 41 10 17 38 22 3 8...

correct output
2413

user output
2413

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
2000 999000000
746120950 772769620 721488968 ...

correct output
1287776

user output
1287776

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
2000 1000000000
621947980 510355354 756705418 ...

correct output
2001000

user output
2001000

Test 11

Group: 3

Verdict: ACCEPTED

input
100000 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
5000050000

user output
5000050000

Test 12

Group: 3

Verdict: ACCEPTED

input
100000 2
3 3 1 3 3 1 1 5 1 2 5 4 1 3 1 ...

correct output
317066

user output
317066

Test 13

Group: 3

Verdict: ACCEPTED

input
100000 10
10 3 6 3 43 60 5 48 15 27 86 4...

correct output
123292

user output
123292

Test 14

Group: 3

Verdict: ACCEPTED

input
100000 999990000
460235639 963048588 47270983 3...

correct output
4946886742

user output
4946886742

Test 15

Group: 3

Verdict: ACCEPTED

input
100000 1000000000
885457070 18257718 927615960 3...

correct output
5000050000

user output
5000050000

Test 16

Group: 3

Verdict: ACCEPTED

input
100000 50000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
3750075000

user output
3750075000

Test 17

Group: 3

Verdict: ACCEPTED

input
100000 50000
100000 99999 99998 99997 99996...

correct output
3750075000

user output
3750075000