Submission #8072059


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

"""
・射影平面 P^2(F_p)
・同一直線上にある点を同じ紙の上に書く
・直線は、P^2(F_p)の点でパラメタライズされる
・(a:b:1) -> a+bp, (a:1:0) -> p^2+a, (1:0:0) -> p^2+p
"""

p = 37; rng = range(p)

inv = [pow(x,p-2,p) for x in range(p)]

def coord_to_idx(x,y,z):
    x %= p; y %= p; z %= p
    if z != 0:
        x *= inv[z]; y *= inv[z]; z = 1; x%=p; y%=p
        return x+y*p+1
    if y != 0:
        x *= inv[y]; x%=p
        return p*p+x+1
    return p*p+p+1

line = []
for a,b in itertools.product(rng,repeat=2):
    # ax+by+z=0となる射影平面上の点(x:y:z)
    if a==0 and b==0:
        pts = [coord_to_idx(x,1,0) for x in rng] + [coord_to_idx(1,0,0)]
        line.append(pts)
        continue
    pts = []
    # 無限遠直線 ax+by=0 上に1つ点がある
    pts.append(coord_to_idx(b,-a,0))
    # アフィン平面上の点。ax+by+z=0 and z=1
    if b != 0:
        pts += [coord_to_idx(x,-(a*x+1)*inv[b],1) for x in rng]
    else:
        # ax+z=0
        pts += [coord_to_idx(1,x,-a) for x in rng]
    line.append(pts)
for a in rng:
    # ax+y=0
    pts = [coord_to_idx(1,-a,x) for x in rng] + [coord_to_idx(0,0,1)]
    line.append(pts)
# x=0
pts = [coord_to_idx(0,x,1) for x in rng] + [coord_to_idx(0,1,0)]
line.append(pts)

print(p*p+p+1,p+1)
for l in line:
    print(' '.join(map(str,l)))

Submission Info

Submission Time
Task F - Distribute Numbers
User maspy
Language Python (3.4.3)
Score 1000
Code Size 1543 Byte
Status AC
Exec Time 79 ms
Memory 5244 KB

Judge Result

Set Name All
Score / Max Score 1000 / 1000
Status
AC × 1
Set Name Test Cases
All 01-01.txt
Case Name Status Exec Time Memory
01-01.txt AC 79 ms 5244 KB