Untitled

mail@pastecode.io avatar
unknown
python
2 years ago
4.1 kB
0
Indexable
Never
import time
import sys


#test_string0 = "2\n1 1 2\n2 2 1\n1 1 2\n2 2 1"
#test_string1 = "2\n1 1 2\n1 2 1\n2 2 1\n2 1 2"
#test_string2 = "3\n1 2 1 3\n2 2 3 1\n3 2 1 3\n1 2 3 1\n2 1 3 2\n3 1 2 3"
#test_string3 = "4\n2 1 2 3 4\n1 1 3 2 4\n3 1 2 3 4\n4 1 2 3 4\n3 4 3 2 1\n4 4 3 2 1\n2 1 2 3 4\n1 1 2 3 4"


N = int(sys.stdin.readline())
Left = 2*N*(N+1)
Data = []
while(Left > 0):
    row = [int(c) for c in sys.stdin.readline().split()]
    Data.extend(row)
    Left -= len(row)



class preferance:
    def __init__(self, n, m):
        self.n = n
        self.m = m
    
    def show(self):
        print(self.n, self.m)
        

class per:
    def __init__(self, id, N):
        self.id = id
        self.pref_list = []
        self.current_partner = None

        for i in range(0, N):
            self.pref_list.append(None)
    
    def show_pref_list(self):
        for pref in self.pref_list:
            pref.show()

class pair:
    def __init__(self, man, woman):
        self.man = man
        self.woman = woman
    
    def show(self):
        print(self.man.id, self.woman.id)


def format(string_list):
    #array_list = string_list.split()
    #N = int(array_list.pop(0))
    #array_list = [int(i) for i in array_list]

    array_list = string_list
    
    W = []
    M = []

    for i in range(0, N * (N + 1)):
        W.append(0)
        M.append(0)
    
   
    woman = False
    f = lambda x: (N + 1) * x - N - 1
    current_number = -1
    k = 0
    for i in range(0, len(array_list)):
        id = array_list[i]
        if(i % (N + 1) == 0):
            k = 0
            if(W[f(id)] == 0):
                W[f(id)] = id
                woman = True
            else:
                M[f(id)] = id
                woman = False
            
            current_number = f(id)
        else:
            k = k + 1
            if(woman):
                W[current_number + k] = id
            else:
                M[current_number + k] = id

           
            
    #print(W)
    #print(M)       
    
    W_person = []
    M_person = []

    #start1 = time.time()
    for i in range(0, N):
        W_person.append(per(i + 1, N))
        M_person.append(per(i + 1, N))
    #end1 = time.time()
    
    #print(end1 - start1)
    
    #start2 = time.time()
    j = 0
    k = 0
    #len(W)
    for i in range(0, len(W)):
        if(i % (N + 1) == 0):
            person1 = W_person[j]
            person2 = M_person[j]
            j = j + 1
            k = 0
        else:
            person1.pref_list[W[i] - 1] = preferance(W[i], i % (N + 1))
            person2.pref_list[k] = preferance(M[i], i % (N + 1))
            k = k + 1
    #end2 = time.time()
    #print(end2 - start2)
    
    return[N, W_person, M_person]

def gs(string):
    
    data = format(string)
    #N = data[0]
    women = data[1]
    p = data[2]
    pairs = []

    for i in range(0, N):
        pairs.append(pair(None, women[i]))
    
    #start3 = time.time()
    while not len(p) == 0:
        m = p.pop(0)
        w_id = m.pref_list[0].n
        m.pref_list.pop(0)
        w = women[w_id - 1]
        
        if w.current_partner == None:
            m.current_partner = w
            w.current_partner = m
            pairs[w_id - 1].man = m
            
        else:
            m_id = m.id
            mw_id = w.current_partner.id
            m_status = w.pref_list[m_id - 1].m
            mw_status = w.pref_list[mw_id - 1].m
            mw = w.current_partner
                
            if m_status < mw_status:
                mw.current_partner = None
                m.current_partner = w
                w.current_partner = m
                pairs[w_id - 1].man = m
                p.append(mw)
                    
            else:
                p.append(m)
    
    #end3 = time.time()
    #print(end3 - start3)
    s = ""
    for i in range(0, N):
        print(pairs[i].man.id)
        s = s + str(pairs[i].man.id)
        s = s + "\n"
    
    #return s
        
        
start = time.time()
gs(Data)
end = time.time()
#print(end - start)