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