108692024-04-17 09:07:0842Évzárópython3Runtime error 38/100777ms135420 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={}
    for i in range(N):
        x,y = list(map(int, input().split()))
        d[f(x,y)] = i
        try: hor[y].append(x)
        except: hor[y]=[x]
        try: ver[x].append(y)
        except: ver[x]=[y]
    res=[True]*N
    graph={}
    for y in hor:
        for i in range(len(hor[y])//2):
            try: graph[f(hor[y][2*i],y)].append(f(hor[y][2*i+1],y))
            except: graph[f(hor[y][2*i],y)] = [f(hor[y][2*i+1],y)]
            try: graph[f(hor[y][2*i+1],y)].append(f(hor[y][2*i],y))
            except: graph[f(hor[y][2*i+1],y)] = [f(hor[y][2*i],y)]
    for x in ver:
        for i in range(len(ver[x])//2):
            try: graph[f(x,ver[x][2*i])].append(f(x,ver[x][2*i+1]))
            except: graph[f(x,ver[x][2*i])] = [f(x,ver[x][2*i+1])]
            try: graph[f(x,ver[x][2*i+1])].append(f(x,ver[x][2*i]))
            except: graph[f(x,ver[x][2*i+1])] = [f(x,ver[x][2*i])]
    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
    #print(''.join(res))
    for x in res:
        if x:
            stdout.write('L')
        else:
            stdout.write('F')
    stdout.write('\n')
        
main()
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted18ms11860 KiB
2Accepted728ms134360 KiB
subtask25/5
3Accepted600ms134440 KiB
4Accepted662ms134808 KiB
subtask30/7
5Accepted600ms134440 KiB
6Accepted662ms134808 KiB
7Accepted614ms135104 KiB
8Runtime error477ms135420 KiB
9Runtime error488ms134952 KiB
10Accepted425ms105304 KiB
subtask40/20
11Runtime error527ms134936 KiB
12Runtime error524ms134800 KiB
13Runtime error524ms134704 KiB
14Runtime error527ms134480 KiB
15Runtime error603ms134416 KiB
16Accepted421ms106100 KiB
subtask513/13
17Accepted18ms14280 KiB
18Accepted18ms14164 KiB
19Accepted17ms14052 KiB
20Accepted17ms14268 KiB
21Accepted17ms14452 KiB
22Accepted17ms14356 KiB
23Accepted17ms14136 KiB
24Accepted17ms14200 KiB
25Accepted17ms14292 KiB
26Accepted18ms14260 KiB
27Accepted18ms14104 KiB
28Accepted18ms14368 KiB
29Accepted17ms14224 KiB
30Accepted17ms14040 KiB
31Accepted17ms14244 KiB
32Accepted17ms14276 KiB
33Accepted17ms14220 KiB
subtask620/20
34Accepted18ms14280 KiB
35Accepted18ms14164 KiB
36Accepted17ms14052 KiB
37Accepted17ms14268 KiB
38Accepted17ms14452 KiB
39Accepted17ms14356 KiB
40Accepted17ms14136 KiB
41Accepted17ms14200 KiB
42Accepted17ms14292 KiB
43Accepted18ms14260 KiB
44Accepted18ms14104 KiB
45Accepted18ms14368 KiB
46Accepted17ms14224 KiB
47Accepted17ms14040 KiB
48Accepted17ms14244 KiB
49Accepted17ms14276 KiB
50Accepted17ms14220 KiB
51Accepted25ms15620 KiB
52Accepted25ms15556 KiB
53Accepted26ms15680 KiB
54Accepted25ms15628 KiB
55Accepted23ms15300 KiB
56Accepted24ms15628 KiB
57Accepted24ms15680 KiB
58Accepted24ms15488 KiB
59Accepted24ms15712 KiB
60Accepted24ms15892 KiB
61Accepted23ms15864 KiB
62Accepted25ms15708 KiB
63Accepted24ms15896 KiB
64Accepted25ms15892 KiB
65Accepted24ms15908 KiB
subtask70/35
66Accepted18ms14280 KiB
67Runtime error595ms133248 KiB
68Accepted600ms134440 KiB
69Accepted662ms134808 KiB
70Accepted614ms135104 KiB
71Runtime error477ms135420 KiB
72Runtime error488ms134952 KiB
73Accepted425ms105304 KiB
74Runtime error527ms134936 KiB
75Runtime error524ms134800 KiB
76Runtime error524ms134704 KiB
77Runtime error527ms134480 KiB
78Runtime error603ms134416 KiB
79Accepted421ms106100 KiB
80Accepted18ms14164 KiB
81Accepted17ms14052 KiB
82Accepted17ms14268 KiB
83Accepted17ms14452 KiB
84Accepted17ms14356 KiB
85Accepted17ms14136 KiB
86Accepted17ms14200 KiB
87Accepted17ms14292 KiB
88Accepted18ms14260 KiB
89Accepted18ms14104 KiB
90Accepted18ms14368 KiB
91Accepted17ms14224 KiB
92Accepted17ms14040 KiB
93Accepted17ms14244 KiB
94Accepted17ms14276 KiB
95Accepted17ms14220 KiB
96Accepted25ms15620 KiB
97Accepted25ms15556 KiB
98Accepted26ms15680 KiB
99Accepted25ms15628 KiB
100Accepted23ms15300 KiB
101Accepted24ms15628 KiB
102Accepted24ms15680 KiB
103Accepted24ms15488 KiB
104Accepted24ms15712 KiB
105Accepted24ms15892 KiB
106Accepted23ms15864 KiB
107Accepted25ms15708 KiB
108Accepted24ms15896 KiB
109Accepted25ms15892 KiB
110Accepted24ms15908 KiB
111Runtime error579ms133384 KiB
112Runtime error579ms133300 KiB
113Accepted777ms132852 KiB
114Runtime error578ms133260 KiB
115Runtime error569ms133092 KiB
116Runtime error573ms132716 KiB
117Runtime error578ms132932 KiB
118Runtime error574ms132888 KiB
119Runtime error566ms132588 KiB
120Runtime error574ms132600 KiB
121Runtime error515ms132792 KiB