CSES - Datatähti 2017 alku - Results
Submission details
Task:Maalarit
Sender:yhyy
Submission time:2016-10-16 22:15:29 +0300
Language:Assembly
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
Test results
testverdicttimegroup
#10.05 s1details
#20.06 s1details
#30.06 s1details
#40.05 s1details
#50.06 s1details
#60.05 s1details
#70.06 s2details
#80.06 s2details
#90.06 s2details
#100.05 s2details
#110.06 s2details
#120.05 s2details
#130.05 s3details
#140.06 s3details
#150.05 s3details
#160.05 s3details
#170.07 s3details
#180.05 s3details
#190.06 s4details
#200.06 s4details
#210.06 s4details
#220.07 s4details
#230.07 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
mov [p+eax], 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]
cmp rax, 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 r13d, [h+rcx*4]
jnl ._a2
dec rcx
mov eax, 1
xor ebx, ebx
cmp eax, [aita+ecx*4]
mov eax, 2
cmove ebx, eax
cmp eax, [aita+ecx*4]
mov eax, 1
cmove ebx, eax
inc ecx
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
inc ecx
inc eax
mov ebx, 1
cmp eax, [aita+ecx*4]
mov eax, 2
cmove ebx, eax
dec ecx
mov [aita+ecx*4], ebx
._a3: loop .a3
mov ecx, 0
jmp ._a4
.a4:
inc ecx
xor eax, eax
cmp eax, [aita+ecx*4]
jne ._a4
mov edx, ecx
dec edx
mov ebx, 1
mov eax, 2
cmp eax, [aita+edx*4]
je ._
add edx, 2
cmp eax, [aita+edx*4]
je ._
mov ebx, 2
._: mov eax, 1
xor edx, edx
dec ecx
cmp eax, [aita+ecx*4]
cmove ebx, edx
add ecx, 2
cmp eax, [aita+ecx*4]
cmove ebx, edx
dec ecx
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...