CSES - Datatähti 2017 alku

Submission details
Task:	Maalarit
Sender:	yhyy
Submission time:	2016-10-16 23:44:42 +0300
Language:	Assembly
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	WRONG ANSWER	0
#2	WRONG ANSWER	0
#3	WRONG ANSWER	0
#4	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.05 s	1	details
#2	ACCEPTED	0.07 s	1	details
#3	ACCEPTED	0.06 s	1	details
#4	WRONG ANSWER	0.06 s	1	details
#5	ACCEPTED	0.06 s	1	details
#6	ACCEPTED	0.07 s	1	details
#7	ACCEPTED	0.05 s	2	details
#8	WRONG ANSWER	0.05 s	2	details
#9	ACCEPTED	0.06 s	2	details
#10	ACCEPTED	0.07 s	2	details
#11	WRONG ANSWER	0.06 s	2	details
#12	ACCEPTED	0.05 s	2	details
#13	WRONG ANSWER	0.06 s	3	details
#14	ACCEPTED	0.06 s	3	details
#15	ACCEPTED	0.05 s	3	details
#16	WRONG ANSWER	0.05 s	3	details
#17	WRONG ANSWER	0.08 s	3	details
#18	ACCEPTED	0.07 s	3	details
#19	WRONG ANSWER	0.07 s	4	details
#20	WRONG ANSWER	0.07 s	4	details
#21	WRONG ANSWER	0.09 s	4	details
#22	WRONG ANSWER	0.07 s	4	details
#23	WRONG ANSWER	0.08 s	4	details
#24	ACCEPTED	0.08 s	4	details

Code

section	.bss
	syote resb 3000000
	t resq 101010
	valit resd 101010
	p resd 101010
	h resd 101010
	aita resd 101010
	edel resd 101010
	seur resd 101010
	puu resd 0x40000
	vasen resq 101010
	oikea resq 101010
	tuloste resb 9000000
section	.text
	global _start
_start:
	mov	rcx, 8000000
	mov	al, 0x20
	mov	rdi, tuloste
.__:	stosb
	loop	.__
	mov	eax, 3
	mov	ebx, 0
	mov	ecx, syote
	mov	edx, 3000000
	int	0x80
	mov	rsi, syote
	call	luku
	mov	r10, r9 	; n
	xor	rdx, rdx	; i
	xor	r14, r14	; b
	xor	r15, r15	; a
.lue:
	call	luku
	inc	rdx
	mov	[h+rdx*4], r9d
        mov	ebx, [h+rdx*4-4]
	cmp	rbx, r9
	cmovg	rbx, r9		; rbx = max(h[i], h[i-1])
	cmp	r14, rbx
	cmovl	r14, rbx	; b=max(b, rbx)
	cmp	r15, r9
	cmovl	r15, r9		; a=max(a, h[i])
	cmp	rdx, r10
	jl	.lue

	mov	rcx, r10
	inc	rcx
	xor	rbx, rbx
	mov	rdx, r10
	inc	rdx
.yhyy:	
	mov	rax, rcx
	dec	rax
	cmp	ebx, [h+eax*4]
	cmovg	ebx, [h+eax*4]
	cmp	r14d, [h+eax*4]		; rbx= min(rbx, h[i])
	jnl	.k
	mov	esi, edx
	sub	esi, eax
	dec	esi
	mov	[p+eax], esi
	inc	esi
	mov	[valit+eax*4], ebx
	and	esi, 1
	imul	ebx, esi
	add	eax, 0x20000
	mov	[puu+eax*4], ebx	; puu[k] = rbx
	call	upd
	mov	ebx, r15d
	mov	rax, rcx
	dec	rax
	mov	[seur+eax*4], edx
	mov	[edel+rdx*4], eax
	mov	rdx, rax
	mov	r9d, [h+eax*4]
	sal	r9, 32
	add	r9, rax
	mov	[t+eax*8], r9
.k:	dec	rcx
	cmp	rcx, 0
	jne	.yhyy
	mov	r13d, [puu+4]
	mov	esi, 1
	mov	edi, r10d
	inc	edi
	call	mergesort
	mov	rdx, 1
.a:
	mov	rax, [t+rdx*8]
	mov	r9, rax
	sar	r9, 32
	cmp	r9, 0
	je	._a
	mov	ecx, eax
	mov	ebx, [valit+eax*4]
	mov	edi, [p+eax*4]
	mov	esi, 0
	add	eax, 0x20000
	mov	[puu+eax*4], esi
	call	upd
	mov	eax, [edel+ecx*4]
	cmp	[valit+eax*4], ebx
	jg	.pyh
	mov	[valit+eax*4], ebx
.pyh:
	inc	edi
	add	[p+eax*4], edi
	mov	edi, [p+eax*4]
	inc	edi
	and	edi, 1
	imul	ebx, edi
	add	eax, 0x20000
	mov	[puu+eax*4], ebx
	call	upd
	mov	eax, [puu+4]
	add	eax, [h+ecx*4]
	mov	ebx, r13d
	add	ebx, r14d
	cmp	ebx, eax
	cmovg	r13d, [puu+4]
	cmovg	r14d, [h+ecx*4]

._a:	inc	rdx	
	cmp	rdx, r10
	jng	.a

	mov	rdi, tuloste
	mov	rax, r15
	;call	tulosta
	add	rax, r14
	;call	tulosta
	add	rax, r13
	call	tulosta
	mov	rax, 3
	call	tulosta
	call	aitageneraattori
.lopeta:
	mov	rdx, rdi
	sub	rdx, tuloste
	mov	rax, 4
	mov	rbx, 1
	mov	rcx, tuloste
	int	0x80
	mov	rax, 1
	mov	rbx, 0
	int	0x80
luku:
	xor	r9, r9
.a:
	xor	rax, rax
	lodsb
	cmp	al, 0x30
	jl	.mm
	cmp	al, 0x39
	jg	.mm
	sub	al, 0x30
	imul	r9, 10
	add	r9, rax
	jmp	.a
.mm:
	cmp	r9, 0
	je	.a
	ret
upd:
.a:
	sar	eax, 1
	sal	eax, 1
	mov	r9d, [puu+eax*4]
	inc	eax
	cmp	r9d, [puu+eax*4]
	cmovl	r9d, [puu+eax*4]
	sar	eax, 1
	mov	[puu+eax*4], r9d
	cmp	eax, 0
	jne	.a
	ret
mergesort:
	push	rbp
	mov	rbp, rsp
	sub	rsp, 12
	cmp	esi, edi
	jnl	.palaa
	mov	[rbp-4], esi  
	mov	[rbp-8], edi  
	mov	edx, esi
	add	edx, edi
	sar	edx, 1        
	mov	[rbp-12], edx
	mov	edi, edx
	call	mergesort
	mov	esi, [rbp-12]
	inc	esi
	mov	edi, [rbp-8]
	call	mergesort
	mov	esi, [rbp-4]
	mov	edi, [rbp-8]
	mov	edx, [rbp-12]
	call	merge
.palaa:
	leave
	ret

merge:
	mov	ecx, edx  
	sub	ecx, esi  
	inc	ecx       
	xor	r9, r9  
	mov	r11d, esi 
.a:
	mov	rax, [t+r11d*8]  
	mov	[vasen+r9d*8], rax 
	inc	r9d  
	inc	r11d  
	loop	.a
	
	mov	rax, 0x7000000000000000
	mov	[vasen+r9d*8], rax
	mov	ecx, edi
	sub	ecx, edx
	xor	r9, r9    
	mov	r11d, edx   
	inc	r11d    
.b:
	mov	rax, [t+r11d*8]
	mov	[oikea+r9d*8], rax
	inc	r9d
	inc	r11d
	loop	.b
	mov	rax, 0x7000000000000000
	mov	[oikea+r9d*8], rax
	mov	ecx, edi
	sub	ecx, esi
	inc	ecx     
	xor	r9, r9
	xor	r11, r11
	mov	r12d, esi
.c:
	mov	rax, [vasen+r9d*8]
	cmp	rax, [oikea+r11d*8]
	jg	.else
	mov	[t+r12d*8], rax
	inc	r12d
	inc	r9d
	jmp	.f
.else:
	mov	rax, [oikea+r11d*8]
	mov	[t+r12d*8], rax
	inc	r12d
	inc	r11d
.f	loop	.c
.palaa:
	ret

tulosta:
	mov	r9, rax
	add	rdi, 18
	std
.a:
	mov	rax, r9
	mov	r9, 0xa
	xor	rdx, rdx
	idiv	r9
	mov	r9, rax
	mov	rax, rdx
	add	al, 0x30
	stosb
	cmp	r9, 0
	jne	.a
	cld
	add	rdi, 19
	mov	al, 0x20
	stosb
	ret

aitageneraattori:
	mov	rcx, r10
.a1:	
	xor	eax, eax
	mov	ebx, 1
	cmp	r14d, [h+ecx*4]
	cmovl	eax, ebx
	mov	[aita+ecx*4], eax
	loop	.a1
	xor	rcx, rcx
.a2:
	inc rcx
	xor	eax, eax
	cmp	eax, [aita+rcx*4]
	jne	._a2
	cmp	eax, [aita+rcx*4-4]
	je	._a2
	cmp	r13d, [h+rcx*4]
	jnl	._a2
	mov	eax, 1
	mov	ebx, 1
	mov	edx, 2
	cmp	eax, [aita+ecx*4-4]
	cmove	ebx, edx
	mov	[aita+ecx*4], ebx
._a2:	cmp	rcx, r10
	jl	.a2
	mov	rcx, r10
.a3:	
	xor	eax, eax
	cmp	eax, [aita+rcx*4]
	jne	._a3
	cmp	r13d, [h+rcx*4]
	jnl	._a3
	mov	eax, 1
	mov	ebx, 1
	cmp	eax, [aita+ecx*4+4]
	mov	eax, 2
	cmove	ebx, eax
	mov	[aita+ecx*4], ebx
._a3:	loop	.a3

	mov	rcx, 0
.a4:
	inc	ecx	
	xor	eax, eax
	cmp	eax, [aita+ecx*4]
	jne	._a4
	mov	eax, 2
	cmp	eax, [aita+ecx*4-4]
	je	._
	cmp	eax, [aita+ecx*4+4]
	je	._
	mov	ebx, 2
	mov	[aita+ecx*4], ebx
	jmp	._a4
._:	
	mov	eax, 1
	mov	ebx, 1
	xor	edx, edx
	cmp	eax, [aita+ecx*4-4]
	cmove	ebx, edx
	cmp	eax, [aita+ecx*4+4]
	cmove	ebx, edx
	mov	[aita+ecx*4], ebx
._a4:	cmp	rcx, r10
	jl	.a4
	mov	rcx, 0
.a5:	inc	rcx
	xor	rax, rax
	mov	eax, [aita+rcx*4]
	inc	eax
	call	tulosta
	cmp	rcx, r10
	jl	.a5
	ret

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
`10 22 54 3 91 69 90 40 29 83 71` view save

correct output
`174 3 2 1 2 1 2 1 2 1 2 1` view save

user output
`174 ...` view save

Test 2

Group: 1

Verdict: ACCEPTED

input
`10 49 3 96 38 90 18 92 74 83 1` view save

correct output
`170 3 1 2 1 2 1 2 1 2 1 2` view save

user output
`170 ...` view save

Test 3

Group: 1

Verdict: ACCEPTED

input
`10 46 3 41 30 16 17 12 93 80 81` view save

correct output
`173 3 2 1 2 1 2 1 2 1 2 1` view save

user output
`173 ...` view save

Test 4

Group: 1

Verdict: WRONG ANSWER

input
`10 46 8 95 85 82 73 82 92 53 90` view save

correct output
`187 3 1 2 1 2 1 2 1 2 1 2` view save

user output
`240 ...` view save

Test 5

Group: 1

Verdict: ACCEPTED

input
`10 41 18 61 59 40 96 5 2 74 38` view save

correct output
`159 3 2 1 2 1 2 1 2 3 1 2` view save

user output
`159 ...` view save

Test 6

Group: 1

Verdict: ACCEPTED

input
`10 1 1 1 1 1 1 1 1 1 1` view save

correct output
`2 3 2 1 2 1 2 1 2 1 2 1` view save

user output
`2 ...` view save

Test 7

Group: 2

Verdict: ACCEPTED

input
`100 1 39 94 5 24 84 84 10 78 61 38...` view save

correct output
`193 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...` view save

user output
`193 ...` view save

Test 8

Group: 2

Verdict: WRONG ANSWER

input
`100 31 73 18 88 49 28 66 5 32 48 9...` view save

correct output
`199 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...` view save

user output
`203 ...` view save

Test 9

Group: 2

Verdict: ACCEPTED

input
`100 45 56 36 60 31 10 23 79 29 17 ...` view save

correct output
`198 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...` view save

user output
`198 ...` view save

Test 10

Group: 2

Verdict: ACCEPTED

input
`100 1 77 70 62 21 68 40 54 90 62 1...` view save

correct output
`194 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...` view save

user output
`194 ...` view save

Test 11

Group: 2

Verdict: WRONG ANSWER

input
`100 4 47 41 81 56 64 12 10 20 100 ...` view save

correct output
`189 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...` view save

user output
`197 ...` view save

Test 12

Group: 2

Verdict: ACCEPTED

input
`10 1 1 1 1 1 1 1 1 1 1` view save

correct output
`2 3 2 1 2 1 2 1 2 1 2 1` view save

user output
`2 ...` view save

Test 13

Group: 3

Verdict: WRONG ANSWER

input
`100 256160448 813097800 167146270 ...` view save

correct output
`1929869257 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...` view save

user output
`1913733137 ...` view save

Test 14

Group: 3

Verdict: ACCEPTED

input
`100 520002672 3542567 24668528 959...` view save

correct output
`1946957555 3 1 2 3 1 2 1 2 1 2 1 2 1 2 1 2 ...` view save

user output
`1946957555 ...` view save

Test 15

Group: 3

Verdict: ACCEPTED

input
`100 483158423 780224665 844754665 ...` view save

correct output
`1959373560 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...` view save

user output
`1959373560 ...` view save

Test 16

Group: 3

Verdict: WRONG ANSWER

input
`100 969647264 128558017 889036329 ...` view save

correct output
`1997942264 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...` view save

user output
`2085681998 ...` view save

Test 17

Group: 3

Verdict: WRONG ANSWER

input
`100 745018527 400495893 635468795 ...` view save

correct output
`1961391143 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...` view save

user output
`1958477594 ...` view save

Test 18

Group: 3

Verdict: ACCEPTED

input
`10 1 1 1 1 1 1 1 1 1 1` view save

correct output
`2 3 2 1 2 1 2 1 2 1 2 1` view save

user output
`2 ...` view save

Test 19

Group: 4

Verdict: WRONG ANSWER

input
`100000 197349274 775463806 263930657 ...` view save

correct output
`1999942635 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...` view save

user output
`2029556808 ...` view save

Test 20

Group: 4

Verdict: WRONG ANSWER

input
`100000 102296405 34648120 320393597 9...` view save

correct output
`1999930943 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...` view save

user output
`2103748312 ...` view save

Test 21

Group: 4

Verdict: WRONG ANSWER

input
`100000 781254921 418252056 502363453 ...` view save

correct output
`1999987794 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...` view save

user output
`2050135703 ...` view save

Test 22

Group: 4

Verdict: WRONG ANSWER

input
`100000 849784881 230439009 455097426 ...` view save

correct output
`1999979439 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...` view save

user output
`2001040101 ...` view save

Test 23

Group: 4

Verdict: WRONG ANSWER

input
`100000 851456132 13422224 537539701 4...` view save

correct output
`1999948226 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...` view save

user output
`2127640222 ...` view save

Test 24

Group: 4

Verdict: ACCEPTED

input
`100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`2 3 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 ...` view save

user output
`2 ...` view save

Datatähti 2017 alku

Maalarit

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Tasks

Submissions (yhyy)