108642024-04-17 08:53:1842Évzárópython3Futási hiba 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()
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva19ms11812 KiB
2Elfogadva722ms134336 KiB
subtask25/5
3Elfogadva666ms134776 KiB
4Elfogadva587ms134792 KiB
subtask30/7
5Elfogadva666ms134776 KiB
6Elfogadva587ms134792 KiB
7Elfogadva667ms135380 KiB
8Futási hiba521ms135284 KiB
9Futási hiba538ms134884 KiB
10Elfogadva412ms105808 KiB
subtask40/20
11Futási hiba596ms134692 KiB
12Futási hiba535ms134648 KiB
13Futási hiba523ms134684 KiB
14Futási hiba592ms134384 KiB
15Futási hiba536ms133988 KiB
16Elfogadva449ms106436 KiB
subtask513/13
17Elfogadva18ms14360 KiB
18Elfogadva17ms14264 KiB
19Elfogadva17ms14232 KiB
20Elfogadva17ms14420 KiB
21Elfogadva17ms14620 KiB
22Elfogadva18ms14632 KiB
23Elfogadva18ms14512 KiB
24Elfogadva17ms14572 KiB
25Elfogadva17ms14860 KiB
26Elfogadva18ms14920 KiB
27Elfogadva18ms14892 KiB
28Elfogadva18ms14712 KiB
29Elfogadva18ms15028 KiB
30Elfogadva18ms14900 KiB
31Elfogadva18ms14932 KiB
32Elfogadva18ms15036 KiB
33Elfogadva17ms14908 KiB
subtask620/20
34Elfogadva18ms14360 KiB
35Elfogadva17ms14264 KiB
36Elfogadva17ms14232 KiB
37Elfogadva17ms14420 KiB
38Elfogadva17ms14620 KiB
39Elfogadva18ms14632 KiB
40Elfogadva18ms14512 KiB
41Elfogadva17ms14572 KiB
42Elfogadva17ms14860 KiB
43Elfogadva18ms14920 KiB
44Elfogadva18ms14892 KiB
45Elfogadva18ms14712 KiB
46Elfogadva18ms15028 KiB
47Elfogadva18ms14900 KiB
48Elfogadva18ms14932 KiB
49Elfogadva18ms15036 KiB
50Elfogadva17ms14908 KiB
51Elfogadva26ms16264 KiB
52Elfogadva26ms16464 KiB
53Elfogadva25ms16392 KiB
54Elfogadva26ms16520 KiB
55Elfogadva24ms16132 KiB
56Elfogadva24ms16112 KiB
57Elfogadva23ms15988 KiB
58Elfogadva23ms16332 KiB
59Elfogadva24ms16348 KiB
60Elfogadva24ms16444 KiB
61Elfogadva24ms16548 KiB
62Elfogadva24ms16680 KiB
63Elfogadva23ms16516 KiB
64Elfogadva25ms16320 KiB
65Elfogadva24ms16296 KiB
subtask70/35
66Elfogadva18ms14360 KiB
67Futási hiba584ms132844 KiB
68Elfogadva666ms134776 KiB
69Elfogadva587ms134792 KiB
70Elfogadva667ms135380 KiB
71Futási hiba521ms135284 KiB
72Futási hiba538ms134884 KiB
73Elfogadva412ms105808 KiB
74Futási hiba596ms134692 KiB
75Futási hiba535ms134648 KiB
76Futási hiba523ms134684 KiB
77Futási hiba592ms134384 KiB
78Futási hiba536ms133988 KiB
79Elfogadva449ms106436 KiB
80Elfogadva17ms14264 KiB
81Elfogadva17ms14232 KiB
82Elfogadva17ms14420 KiB
83Elfogadva17ms14620 KiB
84Elfogadva18ms14632 KiB
85Elfogadva18ms14512 KiB
86Elfogadva17ms14572 KiB
87Elfogadva17ms14860 KiB
88Elfogadva18ms14920 KiB
89Elfogadva18ms14892 KiB
90Elfogadva18ms14712 KiB
91Elfogadva18ms15028 KiB
92Elfogadva18ms14900 KiB
93Elfogadva18ms14932 KiB
94Elfogadva18ms15036 KiB
95Elfogadva17ms14908 KiB
96Elfogadva26ms16264 KiB
97Elfogadva26ms16464 KiB
98Elfogadva25ms16392 KiB
99Elfogadva26ms16520 KiB
100Elfogadva24ms16132 KiB
101Elfogadva24ms16112 KiB
102Elfogadva23ms15988 KiB
103Elfogadva23ms16332 KiB
104Elfogadva24ms16348 KiB
105Elfogadva24ms16444 KiB
106Elfogadva24ms16548 KiB
107Elfogadva24ms16680 KiB
108Elfogadva23ms16516 KiB
109Elfogadva25ms16320 KiB
110Elfogadva24ms16296 KiB
111Futási hiba592ms133056 KiB
112Futási hiba573ms132720 KiB
113Futási hiba573ms133072 KiB
114Futási hiba574ms132864 KiB
115Futási hiba512ms132928 KiB
116Futási hiba569ms132740 KiB
117Futási hiba575ms132868 KiB
118Futási hiba569ms132836 KiB
119Futási hiba563ms132776 KiB
120Futási hiba517ms132672 KiB
121Futási hiba569ms132816 KiB