108672024-04-17 09:02:1942Évzárópython3Futási hiba 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()
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva18ms11836 KiB
2Elfogadva742ms134184 KiB
subtask25/5
3Elfogadva597ms134520 KiB
4Elfogadva603ms134772 KiB
subtask30/7
5Elfogadva597ms134520 KiB
6Elfogadva603ms134772 KiB
7Elfogadva615ms135244 KiB
8Futási hiba477ms135148 KiB
9Futási hiba490ms135036 KiB
10Elfogadva439ms105384 KiB
subtask40/20
11Futási hiba523ms134960 KiB
12Futási hiba524ms135048 KiB
13Futási hiba524ms134976 KiB
14Futási hiba529ms134892 KiB
15Futási hiba529ms134864 KiB
16Elfogadva421ms105512 KiB
subtask513/13
17Elfogadva17ms13148 KiB
18Elfogadva17ms13500 KiB
19Elfogadva17ms13452 KiB
20Elfogadva17ms13688 KiB
21Elfogadva17ms13868 KiB
22Elfogadva17ms13532 KiB
23Elfogadva17ms13612 KiB
24Elfogadva17ms13536 KiB
25Elfogadva17ms13460 KiB
26Elfogadva17ms13532 KiB
27Elfogadva17ms13680 KiB
28Elfogadva17ms13796 KiB
29Elfogadva17ms13708 KiB
30Elfogadva17ms13576 KiB
31Elfogadva17ms13756 KiB
32Elfogadva17ms13752 KiB
33Elfogadva17ms13520 KiB
subtask620/20
34Elfogadva17ms13148 KiB
35Elfogadva17ms13500 KiB
36Elfogadva17ms13452 KiB
37Elfogadva17ms13688 KiB
38Elfogadva17ms13868 KiB
39Elfogadva17ms13532 KiB
40Elfogadva17ms13612 KiB
41Elfogadva17ms13536 KiB
42Elfogadva17ms13460 KiB
43Elfogadva17ms13532 KiB
44Elfogadva17ms13680 KiB
45Elfogadva17ms13796 KiB
46Elfogadva17ms13708 KiB
47Elfogadva17ms13576 KiB
48Elfogadva17ms13756 KiB
49Elfogadva17ms13752 KiB
50Elfogadva17ms13520 KiB
51Elfogadva25ms14980 KiB
52Elfogadva25ms14912 KiB
53Elfogadva25ms14964 KiB
54Elfogadva24ms14916 KiB
55Elfogadva23ms14504 KiB
56Elfogadva23ms14716 KiB
57Elfogadva23ms14656 KiB
58Elfogadva25ms14888 KiB
59Elfogadva24ms15232 KiB
60Elfogadva23ms14984 KiB
61Elfogadva23ms14900 KiB
62Elfogadva23ms15096 KiB
63Elfogadva23ms15100 KiB
64Elfogadva24ms15108 KiB
65Elfogadva23ms14912 KiB
subtask70/35
66Elfogadva17ms13148 KiB
67Futási hiba541ms134408 KiB
68Elfogadva597ms134520 KiB
69Elfogadva603ms134772 KiB
70Elfogadva615ms135244 KiB
71Futási hiba477ms135148 KiB
72Futási hiba490ms135036 KiB
73Elfogadva439ms105384 KiB
74Futási hiba523ms134960 KiB
75Futási hiba524ms135048 KiB
76Futási hiba524ms134976 KiB
77Futási hiba529ms134892 KiB
78Futási hiba529ms134864 KiB
79Elfogadva421ms105512 KiB
80Elfogadva17ms13500 KiB
81Elfogadva17ms13452 KiB
82Elfogadva17ms13688 KiB
83Elfogadva17ms13868 KiB
84Elfogadva17ms13532 KiB
85Elfogadva17ms13612 KiB
86Elfogadva17ms13536 KiB
87Elfogadva17ms13460 KiB
88Elfogadva17ms13532 KiB
89Elfogadva17ms13680 KiB
90Elfogadva17ms13796 KiB
91Elfogadva17ms13708 KiB
92Elfogadva17ms13576 KiB
93Elfogadva17ms13756 KiB
94Elfogadva17ms13752 KiB
95Elfogadva17ms13520 KiB
96Elfogadva25ms14980 KiB
97Elfogadva25ms14912 KiB
98Elfogadva25ms14964 KiB
99Elfogadva24ms14916 KiB
100Elfogadva23ms14504 KiB
101Elfogadva23ms14716 KiB
102Elfogadva23ms14656 KiB
103Elfogadva25ms14888 KiB
104Elfogadva24ms15232 KiB
105Elfogadva23ms14984 KiB
106Elfogadva23ms14900 KiB
107Elfogadva23ms15096 KiB
108Elfogadva23ms15100 KiB
109Elfogadva24ms15108 KiB
110Elfogadva23ms14912 KiB
111Futási hiba541ms134200 KiB
112Elfogadva684ms132476 KiB
113Elfogadva686ms132024 KiB
114Futási hiba532ms134216 KiB
115Futási hiba532ms134440 KiB
116Futási hiba544ms134348 KiB
117Futási hiba532ms134332 KiB
118Futási hiba536ms134428 KiB
119Futási hiba536ms134232 KiB
120Futási hiba532ms134400 KiB
121Futási hiba532ms134348 KiB