OPiMedia

BattleDev November 26, 2020: Question 4 (wrong way)

Nov 26th, 2020 (edited)
95
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python3
  2. # -*- coding: utf-8 -*-
  3.  
  4. """
  5. BattleDev November 26, 2020
  6. Question 4
  7. Wrong way.
  8. See better way in https://pastebin.com/riarp6VG
  9. """
  10.  
  11. import sys
  12.  
  13.  
  14. def main() -> None:
  15.     n, m = map(int, input().split())
  16.  
  17.     xs = tuple(map(int, input().split()))
  18.  
  19.     # print(xs, file=sys.stderr)
  20.  
  21.     assert len(xs) == n
  22.  
  23.     lrs = []
  24.     for line in sys.stdin:
  25.         l, r = map(int, line.split())
  26.         lrs.append((l, r))
  27.  
  28.     assert len(lrs) == m
  29.  
  30.     # print(lrs, file=sys.stderr)
  31.  
  32.     dlrs = dict()
  33.     for l, r in lrs:
  34.         if l not in dlrs:
  35.             dlrs[l] = []
  36.         dlrs[l].append(r)
  37.  
  38.     for rs in dlrs.values():
  39.         rs.sort()
  40.  
  41.     # print(dlrs, file=sys.stderr)
  42.  
  43.     d = {i: 0 for i in range(256)}
  44.     for l, rs in dlrs.items():
  45.         x = 0
  46.         i = l
  47.         for r in rs:
  48.             # while (i <= r) and (x < 255):  # probably the good way, but WTF somewhere
  49.             while i <= r:  # correct but not enough efficient
  50.                 x ^= xs[i]
  51.                 i += 1
  52.  
  53.             d[x] += 1
  54.  
  55.     print(' '.join(str(nb) for nb in d.values()))
  56.  
  57.  
  58. if __name__ == '__main__':
  59.     main()
  60.  
RAW Paste Data