CSES - Datatähti 2017 alku - Results
Submission details
Task:Maalarit
Sender:yhyy
Submission time:2016-10-16 23:20:15 +0300
Language:Assembly
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
Test results
testverdicttimegroup
#10.06 s1details
#20.06 s1details
#30.06 s1details
#40.06 s1details
#50.05 s1details
#60.05 s1details
#70.05 s2details
#80.05 s2details
#90.05 s2details
#100.06 s2details
#110.05 s2details
#120.05 s2details
#130.06 s3details
#140.05 s3details
#150.05 s3details
#160.05 s3details
#170.05 s3details
#180.05 s3details
#190.06 s4details
#200.06 s4details
#210.06 s4details
#220.06 s4details
#230.06 s4details
#240.06 s4details

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	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:

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

correct output
174 3
2 1 2 1 2 1 2 1 2 1 

user output
174...

Test 2

Group: 1

Verdict:

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

correct output
170 3
1 2 1 2 1 2 1 2 1 2 

user output
170...

Test 3

Group: 1

Verdict:

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

correct output
173 3
2 1 2 1 2 1 2 1 2 1 

user output
173...

Test 4

Group: 1

Verdict:

input
10
46 8 95 85 82 73 82 92 53 90

correct output
187 3
1 2 1 2 1 2 1 2 1 2 

user output
240...

Test 5

Group: 1

Verdict:

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

correct output
159 3
2 1 2 1 2 1 2 3 1 2 

user output
159...

Test 6

Group: 1

Verdict:

input
10
1 1 1 1 1 1 1 1 1 1

correct output
2 3
2 1 2 1 2 1 2 1 2 1 

user output
2...

Test 7

Group: 2

Verdict:

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

correct output
193 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

user output
193...

Test 8

Group: 2

Verdict:

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

correct output
199 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

user output
203...

Test 9

Group: 2

Verdict:

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

correct output
198 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

user output
198...

Test 10

Group: 2

Verdict:

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

correct output
194 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

user output
194...

Test 11

Group: 2

Verdict:

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

correct output
189 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

user output
197...

Test 12

Group: 2

Verdict:

input
10
1 1 1 1 1 1 1 1 1 1

correct output
2 3
2 1 2 1 2 1 2 1 2 1 

user output
2...

Test 13

Group: 3

Verdict:

input
100
256160448 813097800 167146270 ...

correct output
1929869257 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

user output
1913733137 ...

Test 14

Group: 3

Verdict:

input
100
520002672 3542567 24668528 959...

correct output
1946957555 3
1 2 3 1 2 1 2 1 2 1 2 1 2 1 2 ...

user output
1946957555 ...

Test 15

Group: 3

Verdict:

input
100
483158423 780224665 844754665 ...

correct output
1959373560 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

user output
1959373560 ...

Test 16

Group: 3

Verdict:

input
100
969647264 128558017 889036329 ...

correct output
1997942264 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

user output
2085681998 ...

Test 17

Group: 3

Verdict:

input
100
745018527 400495893 635468795 ...

correct output
1961391143 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

user output
1958477594 ...

Test 18

Group: 3

Verdict:

input
10
1 1 1 1 1 1 1 1 1 1

correct output
2 3
2 1 2 1 2 1 2 1 2 1 

user output
2...

Test 19

Group: 4

Verdict:

input
100000
197349274 775463806 263930657 ...

correct output
1999942635 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

user output
2029556808 ...

Test 20

Group: 4

Verdict:

input
100000
102296405 34648120 320393597 9...

correct output
1999930943 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

user output
2103748312 ...

Test 21

Group: 4

Verdict:

input
100000
781254921 418252056 502363453 ...

correct output
1999987794 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

user output
2050135703 ...

Test 22

Group: 4

Verdict:

input
100000
849784881 230439009 455097426 ...

correct output
1999979439 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

user output
2001040101 ...

Test 23

Group: 4

Verdict:

input
100000
851456132 13422224 537539701 4...

correct output
1999948226 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...

user output
2127640222 ...

Test 24

Group: 4

Verdict:

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

correct output
2 3
3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 ...

user output
2...