108602024-04-17 08:36:4642Évzárópython3Futási hiba 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()
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva19ms11760 KiB
2Futási hiba503ms136216 KiB
subtask20/5
3Futási hiba519ms135848 KiB
4Futási hiba458ms135940 KiB
subtask30/7
5Futási hiba519ms135848 KiB
6Futási hiba458ms135940 KiB
7Futási hiba545ms135388 KiB
8Futási hiba546ms135588 KiB
9Futási hiba497ms135152 KiB
10Elfogadva467ms108720 KiB
subtask40/20
11Futási hiba688ms134908 KiB
12Futási hiba675ms134776 KiB
13Futási hiba676ms134816 KiB
14Futási hiba563ms134828 KiB
15Futási hiba561ms134520 KiB
16Elfogadva456ms109604 KiB
subtask513/13
17Elfogadva18ms14108 KiB
18Elfogadva18ms14144 KiB
19Elfogadva17ms14256 KiB
20Elfogadva18ms14424 KiB
21Elfogadva18ms14408 KiB
22Elfogadva17ms14180 KiB
23Elfogadva17ms14552 KiB
24Elfogadva18ms14724 KiB
25Elfogadva17ms14436 KiB
26Elfogadva17ms14472 KiB
27Elfogadva17ms14584 KiB
28Elfogadva17ms14548 KiB
29Elfogadva18ms14540 KiB
30Elfogadva18ms14652 KiB
31Elfogadva18ms14756 KiB
32Elfogadva17ms14688 KiB
33Elfogadva18ms14444 KiB
subtask620/20
34Elfogadva18ms14108 KiB
35Elfogadva18ms14144 KiB
36Elfogadva17ms14256 KiB
37Elfogadva18ms14424 KiB
38Elfogadva18ms14408 KiB
39Elfogadva17ms14180 KiB
40Elfogadva17ms14552 KiB
41Elfogadva18ms14724 KiB
42Elfogadva17ms14436 KiB
43Elfogadva17ms14472 KiB
44Elfogadva17ms14584 KiB
45Elfogadva17ms14548 KiB
46Elfogadva18ms14540 KiB
47Elfogadva18ms14652 KiB
48Elfogadva18ms14756 KiB
49Elfogadva17ms14688 KiB
50Elfogadva18ms14444 KiB
51Elfogadva26ms16312 KiB
52Elfogadva25ms16160 KiB
53Elfogadva25ms16060 KiB
54Elfogadva25ms16240 KiB
55Elfogadva24ms16068 KiB
56Elfogadva24ms15940 KiB
57Elfogadva24ms15968 KiB
58Elfogadva24ms16096 KiB
59Elfogadva24ms15996 KiB
60Elfogadva24ms16012 KiB
61Elfogadva25ms15944 KiB
62Elfogadva24ms16060 KiB
63Elfogadva24ms16156 KiB
64Elfogadva24ms16124 KiB
65Elfogadva24ms16128 KiB
subtask70/35
66Elfogadva18ms14108 KiB
67Futási hiba558ms133520 KiB
68Futási hiba519ms135848 KiB
69Futási hiba458ms135940 KiB
70Futási hiba545ms135388 KiB
71Futási hiba546ms135588 KiB
72Futási hiba497ms135152 KiB
73Elfogadva467ms108720 KiB
74Futási hiba688ms134908 KiB
75Futási hiba675ms134776 KiB
76Futási hiba676ms134816 KiB
77Futási hiba563ms134828 KiB
78Futási hiba561ms134520 KiB
79Elfogadva456ms109604 KiB
80Elfogadva18ms14144 KiB
81Elfogadva17ms14256 KiB
82Elfogadva18ms14424 KiB
83Elfogadva18ms14408 KiB
84Elfogadva17ms14180 KiB
85Elfogadva17ms14552 KiB
86Elfogadva18ms14724 KiB
87Elfogadva17ms14436 KiB
88Elfogadva17ms14472 KiB
89Elfogadva17ms14584 KiB
90Elfogadva17ms14548 KiB
91Elfogadva18ms14540 KiB
92Elfogadva18ms14652 KiB
93Elfogadva18ms14756 KiB
94Elfogadva17ms14688 KiB
95Elfogadva18ms14444 KiB
96Elfogadva26ms16312 KiB
97Elfogadva25ms16160 KiB
98Elfogadva25ms16060 KiB
99Elfogadva25ms16240 KiB
100Elfogadva24ms16068 KiB
101Elfogadva24ms15940 KiB
102Elfogadva24ms15968 KiB
103Elfogadva24ms16096 KiB
104Elfogadva24ms15996 KiB
105Elfogadva24ms16012 KiB
106Elfogadva25ms15944 KiB
107Elfogadva24ms16060 KiB
108Elfogadva24ms16156 KiB
109Elfogadva24ms16124 KiB
110Elfogadva24ms16128 KiB
111Futási hiba518ms133420 KiB
112Futási hiba451ms133276 KiB
113Futási hiba449ms133108 KiB
114Futási hiba455ms133136 KiB
115Futási hiba446ms133100 KiB
116Futási hiba451ms132740 KiB
117Futási hiba453ms132732 KiB
118Futási hiba449ms132828 KiB
119Futási hiba449ms132880 KiB
120Futási hiba458ms132896 KiB
121Futási hiba462ms132840 KiB