Submission #2866147


Source Code Expand

n = gets.to_i
ps = (2*n).times.map{ gets.split.map(&:to_i)}
rel = Array.new(2*n+2){[]}
(n...2*n).each{|i|
    n.times{|j|
        if ps[j][0]<ps[i][0] and ps[j][1]<ps[i][1]
           rel[j] << i
        end
    }
    rel[i] << 2*n+1
}
n.times{|i| rel[2*n] << i}
visited = []

find = ->i{
    return [i] if i==2*n+1
    rel[i].each{|j|
        unless visited[j]
            visited[j] = true
            tmp = find[j]
            if tmp
               tmp << i
               return tmp
            end
        end
    }
    return nil
}

retain = ->a{
    a.each_cons(2){|i,j|
        rel[i] << j
        rel[j].delete(i)
    }
}

res = 0
loop{
    seq = find[2*n]
    break unless seq
    visited = []
    retain[seq]
    res += 1
}
p res

Submission Info

Submission Time
Task C - 2D Plane 2N Points
User refle
Language Ruby (2.3.3)
Score 400
Code Size 784 Byte
Status AC
Exec Time 16 ms
Memory 4092 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 5
AC × 17
Set Name Test Cases
Sample example_0, example_1, example_2, example_3, example_4
All example_0, example_1, example_2, example_3, example_4, line_0, line_1, line_2, line_3, maxrand_0, maxrand_1, maxrand_2, maxrand_3, maxrand_4, rand_0, rand_1, rand_2
Case Name Status Exec Time Memory
example_0 AC 7 ms 1788 KB
example_1 AC 7 ms 1788 KB
example_2 AC 7 ms 1788 KB
example_3 AC 7 ms 3836 KB
example_4 AC 7 ms 1788 KB
line_0 AC 11 ms 2172 KB
line_1 AC 8 ms 1788 KB
line_2 AC 7 ms 1788 KB
line_3 AC 7 ms 1788 KB
maxrand_0 AC 14 ms 2300 KB
maxrand_1 AC 16 ms 2428 KB
maxrand_2 AC 14 ms 2300 KB
maxrand_3 AC 16 ms 2300 KB
maxrand_4 AC 14 ms 2300 KB
rand_0 AC 15 ms 4092 KB
rand_1 AC 10 ms 3964 KB
rand_2 AC 11 ms 2172 KB