Submission #146392

---

Source Code Expand

#!/usr/bin/env python2.7

from collections import defaultdict
from itertools import product

def main():
    print solve(150)

def solve(N = 150):
    T = [[' ' for x in range(N)] for y in range(N)]

    xs = defaultdict(set)
    ys = defaultdict(set)

    for s in range(N):
        a = set()
        for i in range(s):
            a.add((s,i))
            a.add((i,s))
        while len(a) > 0:
            #x, y = sorted(a, key=lambda (x, y):len(xs[x]) + len(ys[y]))[0]
            #a.remove((x,y))
            x, y = a.pop()
            for i, j in product(ys[y], xs[x]):
                if T[j][i] == 'O':
                    T[y][x] = '.'
                    break
            else:
                xs[x].add(y)
                ys[y].add(x)
                T[y][x] = 'O'
                
    if False:
        cnt = 0
        for y in range(N):
            for x in range(N):
                if T[y][x] == 'O':
                    cnt += 1
        print cnt

    for y in range(N):
        for x in range(N):
            if T[y][x] == ' ':
                T[y][x] = '.'

    s = [str(N)]
    for y in range(N):
        s.append("".join(T[y]))
    return "\n".join(s)

if __name__ == '__main__':
    main()

Submission Info

Judge Result