108602024-04-17 08:36:4642Évzárópython3Runtime error 33/100688ms136216 KiB
# discrepancy, balanced 2-coloring, IMO6 1986

from sys import stdin, stdout
input=stdin.readline

def main():
    N = int(input())
    d={}
    hor={}
    ver={}
    for i in range(N):
        x,y = list(map(int, input().split()))
        d[(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[(hor[y][2*i],y)].append((hor[y][2*i+1],y))
            except: graph[(hor[y][2*i],y)] = [(hor[y][2*i+1],y)]
            try: graph[(hor[y][2*i+1],y)].append((hor[y][2*i],y))
            except: graph[(hor[y][2*i+1],y)] = [(hor[y][2*i],y)]
    for x in ver:
        for i in range(len(ver[x])//2):
            try: graph[(x,ver[x][2*i])].append((x,ver[x][2*i+1]))
            except: graph[(x,ver[x][2*i])] = [(x,ver[x][2*i+1])]
            try: graph[(x,ver[x][2*i+1])].append((x,ver[x][2*i]))
            except: graph[(x,ver[x][2*i+1])] = [(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
1Accepted19ms11760 KiB
2Runtime error503ms136216 KiB
subtask20/5
3Runtime error519ms135848 KiB
4Runtime error458ms135940 KiB
subtask30/7
5Runtime error519ms135848 KiB
6Runtime error458ms135940 KiB
7Runtime error545ms135388 KiB
8Runtime error546ms135588 KiB
9Runtime error497ms135152 KiB
10Accepted467ms108720 KiB
subtask40/20
11Runtime error688ms134908 KiB
12Runtime error675ms134776 KiB
13Runtime error676ms134816 KiB
14Runtime error563ms134828 KiB
15Runtime error561ms134520 KiB
16Accepted456ms109604 KiB
subtask513/13
17Accepted18ms14108 KiB
18Accepted18ms14144 KiB
19Accepted17ms14256 KiB
20Accepted18ms14424 KiB
21Accepted18ms14408 KiB
22Accepted17ms14180 KiB
23Accepted17ms14552 KiB
24Accepted18ms14724 KiB
25Accepted17ms14436 KiB
26Accepted17ms14472 KiB
27Accepted17ms14584 KiB
28Accepted17ms14548 KiB
29Accepted18ms14540 KiB
30Accepted18ms14652 KiB
31Accepted18ms14756 KiB
32Accepted17ms14688 KiB
33Accepted18ms14444 KiB
subtask620/20
34Accepted18ms14108 KiB
35Accepted18ms14144 KiB
36Accepted17ms14256 KiB
37Accepted18ms14424 KiB
38Accepted18ms14408 KiB
39Accepted17ms14180 KiB
40Accepted17ms14552 KiB
41Accepted18ms14724 KiB
42Accepted17ms14436 KiB
43Accepted17ms14472 KiB
44Accepted17ms14584 KiB
45Accepted17ms14548 KiB
46Accepted18ms14540 KiB
47Accepted18ms14652 KiB
48Accepted18ms14756 KiB
49Accepted17ms14688 KiB
50Accepted18ms14444 KiB
51Accepted26ms16312 KiB
52Accepted25ms16160 KiB
53Accepted25ms16060 KiB
54Accepted25ms16240 KiB
55Accepted24ms16068 KiB
56Accepted24ms15940 KiB
57Accepted24ms15968 KiB
58Accepted24ms16096 KiB
59Accepted24ms15996 KiB
60Accepted24ms16012 KiB
61Accepted25ms15944 KiB
62Accepted24ms16060 KiB
63Accepted24ms16156 KiB
64Accepted24ms16124 KiB
65Accepted24ms16128 KiB
subtask70/35
66Accepted18ms14108 KiB
67Runtime error558ms133520 KiB
68Runtime error519ms135848 KiB
69Runtime error458ms135940 KiB
70Runtime error545ms135388 KiB
71Runtime error546ms135588 KiB
72Runtime error497ms135152 KiB
73Accepted467ms108720 KiB
74Runtime error688ms134908 KiB
75Runtime error675ms134776 KiB
76Runtime error676ms134816 KiB
77Runtime error563ms134828 KiB
78Runtime error561ms134520 KiB
79Accepted456ms109604 KiB
80Accepted18ms14144 KiB
81Accepted17ms14256 KiB
82Accepted18ms14424 KiB
83Accepted18ms14408 KiB
84Accepted17ms14180 KiB
85Accepted17ms14552 KiB
86Accepted18ms14724 KiB
87Accepted17ms14436 KiB
88Accepted17ms14472 KiB
89Accepted17ms14584 KiB
90Accepted17ms14548 KiB
91Accepted18ms14540 KiB
92Accepted18ms14652 KiB
93Accepted18ms14756 KiB
94Accepted17ms14688 KiB
95Accepted18ms14444 KiB
96Accepted26ms16312 KiB
97Accepted25ms16160 KiB
98Accepted25ms16060 KiB
99Accepted25ms16240 KiB
100Accepted24ms16068 KiB
101Accepted24ms15940 KiB
102Accepted24ms15968 KiB
103Accepted24ms16096 KiB
104Accepted24ms15996 KiB
105Accepted24ms16012 KiB
106Accepted25ms15944 KiB
107Accepted24ms16060 KiB
108Accepted24ms16156 KiB
109Accepted24ms16124 KiB
110Accepted24ms16128 KiB
111Runtime error518ms133420 KiB
112Runtime error451ms133276 KiB
113Runtime error449ms133108 KiB
114Runtime error455ms133136 KiB
115Runtime error446ms133100 KiB
116Runtime error451ms132740 KiB
117Runtime error453ms132732 KiB
118Runtime error449ms132828 KiB
119Runtime error449ms132880 KiB
120Runtime error458ms132896 KiB
121Runtime error462ms132840 KiB