108672024-04-17 09:02:1942Évzárópython3Runtime error 38/100742ms135244 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=[0]*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]]=1
        while cur:
            if l%2==0:
                for v in cur:
                    res[d[v]]=1
            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==0:
            stdout.write('L')
        else:
            stdout.write('F')
    stdout.write('\n')
        
main()
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted18ms11836 KiB
2Accepted742ms134184 KiB
subtask25/5
3Accepted597ms134520 KiB
4Accepted603ms134772 KiB
subtask30/7
5Accepted597ms134520 KiB
6Accepted603ms134772 KiB
7Accepted615ms135244 KiB
8Runtime error477ms135148 KiB
9Runtime error490ms135036 KiB
10Accepted439ms105384 KiB
subtask40/20
11Runtime error523ms134960 KiB
12Runtime error524ms135048 KiB
13Runtime error524ms134976 KiB
14Runtime error529ms134892 KiB
15Runtime error529ms134864 KiB
16Accepted421ms105512 KiB
subtask513/13
17Accepted17ms13148 KiB
18Accepted17ms13500 KiB
19Accepted17ms13452 KiB
20Accepted17ms13688 KiB
21Accepted17ms13868 KiB
22Accepted17ms13532 KiB
23Accepted17ms13612 KiB
24Accepted17ms13536 KiB
25Accepted17ms13460 KiB
26Accepted17ms13532 KiB
27Accepted17ms13680 KiB
28Accepted17ms13796 KiB
29Accepted17ms13708 KiB
30Accepted17ms13576 KiB
31Accepted17ms13756 KiB
32Accepted17ms13752 KiB
33Accepted17ms13520 KiB
subtask620/20
34Accepted17ms13148 KiB
35Accepted17ms13500 KiB
36Accepted17ms13452 KiB
37Accepted17ms13688 KiB
38Accepted17ms13868 KiB
39Accepted17ms13532 KiB
40Accepted17ms13612 KiB
41Accepted17ms13536 KiB
42Accepted17ms13460 KiB
43Accepted17ms13532 KiB
44Accepted17ms13680 KiB
45Accepted17ms13796 KiB
46Accepted17ms13708 KiB
47Accepted17ms13576 KiB
48Accepted17ms13756 KiB
49Accepted17ms13752 KiB
50Accepted17ms13520 KiB
51Accepted25ms14980 KiB
52Accepted25ms14912 KiB
53Accepted25ms14964 KiB
54Accepted24ms14916 KiB
55Accepted23ms14504 KiB
56Accepted23ms14716 KiB
57Accepted23ms14656 KiB
58Accepted25ms14888 KiB
59Accepted24ms15232 KiB
60Accepted23ms14984 KiB
61Accepted23ms14900 KiB
62Accepted23ms15096 KiB
63Accepted23ms15100 KiB
64Accepted24ms15108 KiB
65Accepted23ms14912 KiB
subtask70/35
66Accepted17ms13148 KiB
67Runtime error541ms134408 KiB
68Accepted597ms134520 KiB
69Accepted603ms134772 KiB
70Accepted615ms135244 KiB
71Runtime error477ms135148 KiB
72Runtime error490ms135036 KiB
73Accepted439ms105384 KiB
74Runtime error523ms134960 KiB
75Runtime error524ms135048 KiB
76Runtime error524ms134976 KiB
77Runtime error529ms134892 KiB
78Runtime error529ms134864 KiB
79Accepted421ms105512 KiB
80Accepted17ms13500 KiB
81Accepted17ms13452 KiB
82Accepted17ms13688 KiB
83Accepted17ms13868 KiB
84Accepted17ms13532 KiB
85Accepted17ms13612 KiB
86Accepted17ms13536 KiB
87Accepted17ms13460 KiB
88Accepted17ms13532 KiB
89Accepted17ms13680 KiB
90Accepted17ms13796 KiB
91Accepted17ms13708 KiB
92Accepted17ms13576 KiB
93Accepted17ms13756 KiB
94Accepted17ms13752 KiB
95Accepted17ms13520 KiB
96Accepted25ms14980 KiB
97Accepted25ms14912 KiB
98Accepted25ms14964 KiB
99Accepted24ms14916 KiB
100Accepted23ms14504 KiB
101Accepted23ms14716 KiB
102Accepted23ms14656 KiB
103Accepted25ms14888 KiB
104Accepted24ms15232 KiB
105Accepted23ms14984 KiB
106Accepted23ms14900 KiB
107Accepted23ms15096 KiB
108Accepted23ms15100 KiB
109Accepted24ms15108 KiB
110Accepted23ms14912 KiB
111Runtime error541ms134200 KiB
112Accepted684ms132476 KiB
113Accepted686ms132024 KiB
114Runtime error532ms134216 KiB
115Runtime error532ms134440 KiB
116Runtime error544ms134348 KiB
117Runtime error532ms134332 KiB
118Runtime error536ms134428 KiB
119Runtime error536ms134232 KiB
120Runtime error532ms134400 KiB
121Runtime error532ms134348 KiB