Submission #10,870

2024-04-17 09:23:01

python3

Accepted 100/100

792ms

116468 KiB

# discrepancy, balanced 2-coloring, IMO6 1986

from sys import stdin, stdout
input=stdin.readline

def f(x,y):
    return 10**9*x+y

#def g(c):
#    return c//10**9,c%10**9

def main():
    N = int(input())
    d={}
    hor={}
    ver={}
    graph={}
    for i in range(N):
        x,y = list(map(int, input().split()))
        d[f(x,y)] = i
        try:
            xx=hor.pop(y)
            try: graph[f(x,y)].append(f(xx,y))
            except: graph[f(x,y)] = [f(xx,y)]
            try: graph[f(xx,y)].append(f(x,y))
            except: graph[f(xx,y)] = [f(x,y)]
        except: hor[y]=x
        try:
            yy=ver.pop(x)
            try: graph[f(x,y)].append(f(x,yy))
            except: graph[f(x,y)] = [f(x,yy)]
            try: graph[f(x,yy)].append(f(x,y))
            except: graph[f(x,yy)] = [f(x,y)]
        except: ver[x]=y
    res=[True]*N
    while graph:
        v,cur=graph.popitem()
        l=1
        res[d[v]]=False
        while cur:
            if l%2==0:
                for v in cur:
                    res[d[v]]=False
            tmp=[]
            for v in cur:
                if v in graph:
                    sz=graph.pop(v)
                    for w in sz:
                        if w in graph:
                            tmp.append(w)
            cur=tmp
            l+=1
    for x in res:
        if x:
            stdout.write('L')
        else:
            stdout.write('F')
    stdout.write('\n')
        
main()

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	18ms	11828 KiB
		2	Accepted	740ms	103944 KiB
subtask2	5/5
		3	Accepted	505ms	107428 KiB
		4	Accepted	551ms	107552 KiB
subtask3	7/7
		5	Accepted	505ms	107428 KiB
		6	Accepted	551ms	107552 KiB
		7	Accepted	552ms	107752 KiB
		8	Accepted	564ms	107712 KiB
		9	Accepted	555ms	106320 KiB
		10	Accepted	317ms	73328 KiB
subtask4	20/20
		11	Accepted	787ms	112576 KiB
		12	Accepted	792ms	112856 KiB
		13	Accepted	791ms	113120 KiB
		14	Accepted	792ms	113028 KiB
		15	Accepted	768ms	116468 KiB
		16	Accepted	314ms	74248 KiB
subtask5	13/13
		17	Accepted	18ms	13636 KiB
		18	Accepted	18ms	13544 KiB
		19	Accepted	17ms	13376 KiB
		20	Accepted	18ms	13596 KiB
		21	Accepted	18ms	13808 KiB
		22	Accepted	18ms	13560 KiB
		23	Accepted	18ms	13772 KiB
		24	Accepted	18ms	13748 KiB
		25	Accepted	18ms	13756 KiB
		26	Accepted	17ms	13356 KiB
		27	Accepted	17ms	13620 KiB
		28	Accepted	18ms	13776 KiB
		29	Accepted	17ms	14036 KiB
		30	Accepted	17ms	14272 KiB
		31	Accepted	18ms	14320 KiB
		32	Accepted	18ms	14220 KiB
		33	Accepted	17ms	14572 KiB
subtask6	20/20
		34	Accepted	18ms	13636 KiB
		35	Accepted	18ms	13544 KiB
		36	Accepted	17ms	13376 KiB
		37	Accepted	18ms	13596 KiB
		38	Accepted	18ms	13808 KiB
		39	Accepted	18ms	13560 KiB
		40	Accepted	18ms	13772 KiB
		41	Accepted	18ms	13748 KiB
		42	Accepted	18ms	13756 KiB
		43	Accepted	17ms	13356 KiB
		44	Accepted	17ms	13620 KiB
		45	Accepted	18ms	13776 KiB
		46	Accepted	17ms	14036 KiB
		47	Accepted	17ms	14272 KiB
		48	Accepted	18ms	14320 KiB
		49	Accepted	18ms	14220 KiB
		50	Accepted	17ms	14572 KiB
		51	Accepted	24ms	15624 KiB
		52	Accepted	23ms	15368 KiB
		53	Accepted	24ms	15692 KiB
		54	Accepted	24ms	15688 KiB
		55	Accepted	24ms	15728 KiB
		56	Accepted	24ms	15896 KiB
		57	Accepted	24ms	15824 KiB
		58	Accepted	24ms	15788 KiB
		59	Accepted	24ms	15944 KiB
		60	Accepted	24ms	15784 KiB
		61	Accepted	24ms	15636 KiB
		62	Accepted	24ms	15516 KiB
		63	Accepted	24ms	15652 KiB
		64	Accepted	23ms	15608 KiB
		65	Accepted	24ms	15956 KiB
subtask7	35/35
		66	Accepted	18ms	13636 KiB
		67	Accepted	740ms	106724 KiB
		68	Accepted	505ms	107428 KiB
		69	Accepted	551ms	107552 KiB
		70	Accepted	552ms	107752 KiB
		71	Accepted	564ms	107712 KiB
		72	Accepted	555ms	106320 KiB
		73	Accepted	317ms	73328 KiB
		74	Accepted	787ms	112576 KiB
		75	Accepted	792ms	112856 KiB
		76	Accepted	791ms	113120 KiB
		77	Accepted	792ms	113028 KiB
		78	Accepted	768ms	116468 KiB
		79	Accepted	314ms	74248 KiB
		80	Accepted	18ms	13544 KiB
		81	Accepted	17ms	13376 KiB
		82	Accepted	18ms	13596 KiB
		83	Accepted	18ms	13808 KiB
		84	Accepted	18ms	13560 KiB
		85	Accepted	18ms	13772 KiB
		86	Accepted	18ms	13748 KiB
		87	Accepted	18ms	13756 KiB
		88	Accepted	17ms	13356 KiB
		89	Accepted	17ms	13620 KiB
		90	Accepted	18ms	13776 KiB
		91	Accepted	17ms	14036 KiB
		92	Accepted	17ms	14272 KiB
		93	Accepted	18ms	14320 KiB
		94	Accepted	18ms	14220 KiB
		95	Accepted	17ms	14572 KiB
		96	Accepted	24ms	15624 KiB
		97	Accepted	23ms	15368 KiB
		98	Accepted	24ms	15692 KiB
		99	Accepted	24ms	15688 KiB
		100	Accepted	24ms	15728 KiB
		101	Accepted	24ms	15896 KiB
		102	Accepted	24ms	15824 KiB
		103	Accepted	24ms	15788 KiB
		104	Accepted	24ms	15944 KiB
		105	Accepted	24ms	15784 KiB
		106	Accepted	24ms	15636 KiB
		107	Accepted	24ms	15516 KiB
		108	Accepted	24ms	15652 KiB
		109	Accepted	23ms	15608 KiB
		110	Accepted	24ms	15956 KiB
		111	Accepted	707ms	106252 KiB
		112	Accepted	684ms	103560 KiB
		113	Accepted	685ms	103116 KiB
		114	Accepted	712ms	106220 KiB
		115	Accepted	735ms	106108 KiB
		116	Accepted	660ms	105900 KiB
		117	Accepted	661ms	106400 KiB
		118	Accepted	661ms	106188 KiB
		119	Accepted	734ms	105960 KiB
		120	Accepted	736ms	106788 KiB
		121	Accepted	657ms	106356 KiB