fork download
copy 
  1. def reader(inFile):
  2.     dummy = inFile.getInt()
  3.     return (inFile.getInts(), inFile.getInts())
  4.  
  5. class Queue:
  6.     def __init__(self, x):
  7.         self.q = x
  8.         self.qat = 0
  9.         self.qlen = len(x)
  10.  
  11.     def pop(self):
  12.         self.qat += 1
  13.         return self.q[self.qat - 1]
  14.  
  15.     def elements(self):
  16.         while (not self.empty()):
  17.             yield self.pop()
  18.  
  19.     def push(self, x):
  20.         self.q.append(x)
  21.         self.qlen += 1
  22.  
  23.     def empty(self):
  24.         return self.qat == self.qlen
  25.  
  26. def solver((a,b)):
  27.     N = len(a)
  28.     lwrs = [[] for i in xrange(N)] 
  29.     uprs = [[] for i in xrange(N)]
  30.     last = {}
  31.     for i in xrange(N):
  32.         if last.has_key(a[i]):
  33.             lwrs[last[a[i]]] += [i]
  34.         last[a[i]] = i
  35.         if a[i] > 1:
  36.             lwrs[i] += [last[a[i]-1]]
  37.             uprs[last[a[i]-1]] += [i]
  38.     last = {}
  39.     for i in xrange(N - 1, -1, -1):
  40.         if last.has_key(b[i]):
  41.             lwrs[last[b[i]]] += [i]
  42.         last[b[i]] = i
  43.         if b[i] > 1:
  44.             lwrs[i] += [last[b[i]-1]]
  45.             uprs[last[b[i]-1]] += [i]
  46.  
  47.     ans = [0] * N
  48.     for i in xrange(N):
  49.         inQ = [False] * N
  50.         q = Queue([i])
  51.         inQ[i] = True
  52.         for j in q.elements():
  53.             for l in lwrs[j]:
  54.                 if not inQ[l]:
  55.                     q.push(l)
  56.                     inQ[l] = True
  57.         ans[i] = q.qlen
  58.         for j in xrange(N):
  59.             if not inQ[j]:
  60.                 lwrs[j] += [i]
  61.     return " ".join([str(z) for z in ans])
  62.  
  63. if __name__ == "__main__":
  64.     from GCJ import GCJ
  65.     GCJ(reader, solver, "/Users/lpebody/gcj/2013_2/c/", "c").run()
  66.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ELVrbk
language:
Python (cpython 2.7.16)
created:
10 years ago
visibility:
secret

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!