108692024-04-17 09:07:0842Évzárópython3Futási hiba 38/100777ms135420 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=[True]*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]]=False
        while cur:
            if l%2==0:
                for v in cur:
                    res[d[v]]=False
            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:
            stdout.write('L')
        else:
            stdout.write('F')
    stdout.write('\n')
        
main()
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva18ms11860 KiB
2Elfogadva728ms134360 KiB
subtask25/5
3Elfogadva600ms134440 KiB
4Elfogadva662ms134808 KiB
subtask30/7
5Elfogadva600ms134440 KiB
6Elfogadva662ms134808 KiB
7Elfogadva614ms135104 KiB
8Futási hiba477ms135420 KiB
9Futási hiba488ms134952 KiB
10Elfogadva425ms105304 KiB
subtask40/20
11Futási hiba527ms134936 KiB
12Futási hiba524ms134800 KiB
13Futási hiba524ms134704 KiB
14Futási hiba527ms134480 KiB
15Futási hiba603ms134416 KiB
16Elfogadva421ms106100 KiB
subtask513/13
17Elfogadva18ms14280 KiB
18Elfogadva18ms14164 KiB
19Elfogadva17ms14052 KiB
20Elfogadva17ms14268 KiB
21Elfogadva17ms14452 KiB
22Elfogadva17ms14356 KiB
23Elfogadva17ms14136 KiB
24Elfogadva17ms14200 KiB
25Elfogadva17ms14292 KiB
26Elfogadva18ms14260 KiB
27Elfogadva18ms14104 KiB
28Elfogadva18ms14368 KiB
29Elfogadva17ms14224 KiB
30Elfogadva17ms14040 KiB
31Elfogadva17ms14244 KiB
32Elfogadva17ms14276 KiB
33Elfogadva17ms14220 KiB
subtask620/20
34Elfogadva18ms14280 KiB
35Elfogadva18ms14164 KiB
36Elfogadva17ms14052 KiB
37Elfogadva17ms14268 KiB
38Elfogadva17ms14452 KiB
39Elfogadva17ms14356 KiB
40Elfogadva17ms14136 KiB
41Elfogadva17ms14200 KiB
42Elfogadva17ms14292 KiB
43Elfogadva18ms14260 KiB
44Elfogadva18ms14104 KiB
45Elfogadva18ms14368 KiB
46Elfogadva17ms14224 KiB
47Elfogadva17ms14040 KiB
48Elfogadva17ms14244 KiB
49Elfogadva17ms14276 KiB
50Elfogadva17ms14220 KiB
51Elfogadva25ms15620 KiB
52Elfogadva25ms15556 KiB
53Elfogadva26ms15680 KiB
54Elfogadva25ms15628 KiB
55Elfogadva23ms15300 KiB
56Elfogadva24ms15628 KiB
57Elfogadva24ms15680 KiB
58Elfogadva24ms15488 KiB
59Elfogadva24ms15712 KiB
60Elfogadva24ms15892 KiB
61Elfogadva23ms15864 KiB
62Elfogadva25ms15708 KiB
63Elfogadva24ms15896 KiB
64Elfogadva25ms15892 KiB
65Elfogadva24ms15908 KiB
subtask70/35
66Elfogadva18ms14280 KiB
67Futási hiba595ms133248 KiB
68Elfogadva600ms134440 KiB
69Elfogadva662ms134808 KiB
70Elfogadva614ms135104 KiB
71Futási hiba477ms135420 KiB
72Futási hiba488ms134952 KiB
73Elfogadva425ms105304 KiB
74Futási hiba527ms134936 KiB
75Futási hiba524ms134800 KiB
76Futási hiba524ms134704 KiB
77Futási hiba527ms134480 KiB
78Futási hiba603ms134416 KiB
79Elfogadva421ms106100 KiB
80Elfogadva18ms14164 KiB
81Elfogadva17ms14052 KiB
82Elfogadva17ms14268 KiB
83Elfogadva17ms14452 KiB
84Elfogadva17ms14356 KiB
85Elfogadva17ms14136 KiB
86Elfogadva17ms14200 KiB
87Elfogadva17ms14292 KiB
88Elfogadva18ms14260 KiB
89Elfogadva18ms14104 KiB
90Elfogadva18ms14368 KiB
91Elfogadva17ms14224 KiB
92Elfogadva17ms14040 KiB
93Elfogadva17ms14244 KiB
94Elfogadva17ms14276 KiB
95Elfogadva17ms14220 KiB
96Elfogadva25ms15620 KiB
97Elfogadva25ms15556 KiB
98Elfogadva26ms15680 KiB
99Elfogadva25ms15628 KiB
100Elfogadva23ms15300 KiB
101Elfogadva24ms15628 KiB
102Elfogadva24ms15680 KiB
103Elfogadva24ms15488 KiB
104Elfogadva24ms15712 KiB
105Elfogadva24ms15892 KiB
106Elfogadva23ms15864 KiB
107Elfogadva25ms15708 KiB
108Elfogadva24ms15896 KiB
109Elfogadva25ms15892 KiB
110Elfogadva24ms15908 KiB
111Futási hiba579ms133384 KiB
112Futási hiba579ms133300 KiB
113Elfogadva777ms132852 KiB
114Futási hiba578ms133260 KiB
115Futási hiba569ms133092 KiB
116Futási hiba573ms132716 KiB
117Futási hiba578ms132932 KiB
118Futási hiba574ms132888 KiB
119Futási hiba566ms132588 KiB
120Futási hiba574ms132600 KiB
121Futási hiba515ms132792 KiB