fork download
copy 
  1. import sys
  2.  
  3. with sys.stdin as f:
  4.     ncases = int(f.readline())
  5.     for caseix in range(ncases):
  6.         try:
  7.             nflavours = int(f.readline())
  8.             nclients = int(f.readline())
  9.             preferences = []
  10.             preferences_count = []
  11.             preferences_index = [0 for _x in xrange(nclients)]
  12.             flavour_match = [[] for _x in xrange(nflavours)]
  13.             flavour = [0 for _x in xrange(nflavours)]
  14.             malted = []
  15.             for clientix in range(nclients):
  16.                 data = f.readline().strip().split(' ')
  17.                 preferences_count.append(int(data[0]))
  18.                 lst = data[1:]
  19.                 l = [int(lst[ix]) - 1 for ix in range(len(lst)) if ix%2==0]
  20.                 s = [int(lst[ix]) for ix in range(len(lst)) if ix%2==1]
  21.                 preference = list(zip(l,s))
  22.                 preference.sort(key=lambda p: p[1])
  23.                 preferences.append(preference)
  24.                 if len(preference) == 1 and preference[0][1] == 1:
  25.                     malted.append(preference[0][0])
  26.                 else:
  27.                     flavour_match[preference[0][0]].append(clientix)
  28.             while len(malted) != 0:
  29.                 new_malted = []
  30.                 for x in malted:
  31.                     if flavour[x] == 1:
  32.                         continue
  33.                     flavour[x] = 1
  34.                     for client in flavour_match[x]:
  35.                         preferences_index[client] = preferences_index[client] + 1
  36.                         while preferences_index[client] < preferences_count[client]:
  37.                             if preferences[client][preferences_index[client]][1] == 1:
  38.                                 new_malted.append(preferences[client][preferences_index[client]][0])
  39.                                 break
  40.                             elif flavour[preferences[client][preferences_index[client]][0]] == 1:
  41.                                 preferences_index[client] = preferences_index[client] + 1
  42.                                 continue
  43.                             flavour_match[preferences[client][preferences_index[client]][0]].append(client)
  44.                             break
  45.                         if preferences_index[client] >= preferences_count[client]:
  46.                             raise Exception
  47.                 malted = new_malted
  48.         except:
  49.             print 'Case #{}: IMPOSSIBLE'.format(caseix +1)
  50.         else:
  51.             print 'Case #{}:'.format(caseix +1),
  52.             for x in flavour:
  53.                 print x,
  54.             print ""
  55.  
Success #stdin #stdout 0.02s 9024KB
comments (?)
stdin
copy 
3
5
3
1 1 1
2 1 0 2 0
1 5 0
1
2
1 1 0
1 1 1
6
6
1 1 1
1 2 1
1 3 1
3 4 0 5 0 6 1
4 1 0 2 0 3 0 4 1
4 1 0 2 0 3 0 5 1
stdout
copy 
Case #1: 1 0 0 0 0 
Case #2: IMPOSSIBLE
Case #3: 1 1 1 1 1 1
https://ideone.com/nH1JWv
language:
Python (cpython 2.7.16)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!