108642024-04-17 08:53:1842Évzárópython3Runtime error 38/100722ms135380 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=['L']*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]]='F'
        while cur:
            if l%2==0:
                for v in cur:
                    res[d[v]]='F'
            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))
        
main()
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted19ms11812 KiB
2Accepted722ms134336 KiB
subtask25/5
3Accepted666ms134776 KiB
4Accepted587ms134792 KiB
subtask30/7
5Accepted666ms134776 KiB
6Accepted587ms134792 KiB
7Accepted667ms135380 KiB
8Runtime error521ms135284 KiB
9Runtime error538ms134884 KiB
10Accepted412ms105808 KiB
subtask40/20
11Runtime error596ms134692 KiB
12Runtime error535ms134648 KiB
13Runtime error523ms134684 KiB
14Runtime error592ms134384 KiB
15Runtime error536ms133988 KiB
16Accepted449ms106436 KiB
subtask513/13
17Accepted18ms14360 KiB
18Accepted17ms14264 KiB
19Accepted17ms14232 KiB
20Accepted17ms14420 KiB
21Accepted17ms14620 KiB
22Accepted18ms14632 KiB
23Accepted18ms14512 KiB
24Accepted17ms14572 KiB
25Accepted17ms14860 KiB
26Accepted18ms14920 KiB
27Accepted18ms14892 KiB
28Accepted18ms14712 KiB
29Accepted18ms15028 KiB
30Accepted18ms14900 KiB
31Accepted18ms14932 KiB
32Accepted18ms15036 KiB
33Accepted17ms14908 KiB
subtask620/20
34Accepted18ms14360 KiB
35Accepted17ms14264 KiB
36Accepted17ms14232 KiB
37Accepted17ms14420 KiB
38Accepted17ms14620 KiB
39Accepted18ms14632 KiB
40Accepted18ms14512 KiB
41Accepted17ms14572 KiB
42Accepted17ms14860 KiB
43Accepted18ms14920 KiB
44Accepted18ms14892 KiB
45Accepted18ms14712 KiB
46Accepted18ms15028 KiB
47Accepted18ms14900 KiB
48Accepted18ms14932 KiB
49Accepted18ms15036 KiB
50Accepted17ms14908 KiB
51Accepted26ms16264 KiB
52Accepted26ms16464 KiB
53Accepted25ms16392 KiB
54Accepted26ms16520 KiB
55Accepted24ms16132 KiB
56Accepted24ms16112 KiB
57Accepted23ms15988 KiB
58Accepted23ms16332 KiB
59Accepted24ms16348 KiB
60Accepted24ms16444 KiB
61Accepted24ms16548 KiB
62Accepted24ms16680 KiB
63Accepted23ms16516 KiB
64Accepted25ms16320 KiB
65Accepted24ms16296 KiB
subtask70/35
66Accepted18ms14360 KiB
67Runtime error584ms132844 KiB
68Accepted666ms134776 KiB
69Accepted587ms134792 KiB
70Accepted667ms135380 KiB
71Runtime error521ms135284 KiB
72Runtime error538ms134884 KiB
73Accepted412ms105808 KiB
74Runtime error596ms134692 KiB
75Runtime error535ms134648 KiB
76Runtime error523ms134684 KiB
77Runtime error592ms134384 KiB
78Runtime error536ms133988 KiB
79Accepted449ms106436 KiB
80Accepted17ms14264 KiB
81Accepted17ms14232 KiB
82Accepted17ms14420 KiB
83Accepted17ms14620 KiB
84Accepted18ms14632 KiB
85Accepted18ms14512 KiB
86Accepted17ms14572 KiB
87Accepted17ms14860 KiB
88Accepted18ms14920 KiB
89Accepted18ms14892 KiB
90Accepted18ms14712 KiB
91Accepted18ms15028 KiB
92Accepted18ms14900 KiB
93Accepted18ms14932 KiB
94Accepted18ms15036 KiB
95Accepted17ms14908 KiB
96Accepted26ms16264 KiB
97Accepted26ms16464 KiB
98Accepted25ms16392 KiB
99Accepted26ms16520 KiB
100Accepted24ms16132 KiB
101Accepted24ms16112 KiB
102Accepted23ms15988 KiB
103Accepted23ms16332 KiB
104Accepted24ms16348 KiB
105Accepted24ms16444 KiB
106Accepted24ms16548 KiB
107Accepted24ms16680 KiB
108Accepted23ms16516 KiB
109Accepted25ms16320 KiB
110Accepted24ms16296 KiB
111Runtime error592ms133056 KiB
112Runtime error573ms132720 KiB
113Runtime error573ms133072 KiB
114Runtime error574ms132864 KiB
115Runtime error512ms132928 KiB
116Runtime error569ms132740 KiB
117Runtime error575ms132868 KiB
118Runtime error569ms132836 KiB
119Runtime error563ms132776 KiB
120Runtime error517ms132672 KiB
121Runtime error569ms132816 KiB