108582024-04-17 08:27:4242Évzárópython3Futási hiba 33/100657ms135896 KiB
# discrepancy, balanced 2-coloring, IMO6 1986

from sys import stdin, stdout
input=stdin.readline

def main():
    N = int(input())
    points=[]
    d={}
    hor={}
    ver={}
    for i in range(N):
        x,y = list(map(int, input().split()))
        d[(x,y)] = len(points)
        points.append((x,y))
        try: hor[y].append(x)
        except: hor[y]=[x]
        try: ver[x].append(y)
        except: ver[x]=[y]
    res=['L']*len(points)
    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
1Elfogadva18ms11872 KiB
2Futási hiba465ms135896 KiB
subtask20/5
3Futási hiba509ms135884 KiB
4Futási hiba597ms135728 KiB
subtask30/7
5Futási hiba509ms135884 KiB
6Futási hiba597ms135728 KiB
7Futási hiba610ms135576 KiB
8Futási hiba521ms135124 KiB
9Futási hiba541ms135284 KiB
10Elfogadva646ms122740 KiB
subtask40/20
11Futási hiba554ms135072 KiB
12Futási hiba657ms134932 KiB
13Futási hiba538ms134632 KiB
14Futási hiba540ms134572 KiB
15Futási hiba540ms134676 KiB
16Elfogadva546ms123416 KiB
subtask513/13
17Elfogadva17ms13784 KiB
18Elfogadva17ms14040 KiB
19Elfogadva17ms14192 KiB
20Elfogadva17ms14152 KiB
21Elfogadva17ms14332 KiB
22Elfogadva17ms14124 KiB
23Elfogadva17ms14404 KiB
24Elfogadva17ms14660 KiB
25Elfogadva17ms14368 KiB
26Elfogadva17ms14232 KiB
27Elfogadva17ms14520 KiB
28Elfogadva17ms14476 KiB
29Elfogadva17ms14312 KiB
30Elfogadva17ms14340 KiB
31Elfogadva17ms14356 KiB
32Elfogadva17ms14352 KiB
33Elfogadva17ms14644 KiB
subtask620/20
34Elfogadva17ms13784 KiB
35Elfogadva17ms14040 KiB
36Elfogadva17ms14192 KiB
37Elfogadva17ms14152 KiB
38Elfogadva17ms14332 KiB
39Elfogadva17ms14124 KiB
40Elfogadva17ms14404 KiB
41Elfogadva17ms14660 KiB
42Elfogadva17ms14368 KiB
43Elfogadva17ms14232 KiB
44Elfogadva17ms14520 KiB
45Elfogadva17ms14476 KiB
46Elfogadva17ms14312 KiB
47Elfogadva17ms14340 KiB
48Elfogadva17ms14356 KiB
49Elfogadva17ms14352 KiB
50Elfogadva17ms14644 KiB
51Elfogadva25ms16184 KiB
52Elfogadva24ms15964 KiB
53Elfogadva24ms15976 KiB
54Elfogadva24ms16084 KiB
55Elfogadva24ms15916 KiB
56Elfogadva25ms15688 KiB
57Elfogadva24ms15964 KiB
58Elfogadva24ms15892 KiB
59Elfogadva24ms15808 KiB
60Elfogadva23ms15692 KiB
61Elfogadva24ms15852 KiB
62Elfogadva24ms15912 KiB
63Elfogadva24ms15668 KiB
64Elfogadva24ms15904 KiB
65Elfogadva24ms15868 KiB
subtask70/35
66Elfogadva17ms13784 KiB
67Futási hiba444ms133604 KiB
68Futási hiba509ms135884 KiB
69Futási hiba597ms135728 KiB
70Futási hiba610ms135576 KiB
71Futási hiba521ms135124 KiB
72Futási hiba541ms135284 KiB
73Elfogadva646ms122740 KiB
74Futási hiba554ms135072 KiB
75Futási hiba657ms134932 KiB
76Futási hiba538ms134632 KiB
77Futási hiba540ms134572 KiB
78Futási hiba540ms134676 KiB
79Elfogadva546ms123416 KiB
80Elfogadva17ms14040 KiB
81Elfogadva17ms14192 KiB
82Elfogadva17ms14152 KiB
83Elfogadva17ms14332 KiB
84Elfogadva17ms14124 KiB
85Elfogadva17ms14404 KiB
86Elfogadva17ms14660 KiB
87Elfogadva17ms14368 KiB
88Elfogadva17ms14232 KiB
89Elfogadva17ms14520 KiB
90Elfogadva17ms14476 KiB
91Elfogadva17ms14312 KiB
92Elfogadva17ms14340 KiB
93Elfogadva17ms14356 KiB
94Elfogadva17ms14352 KiB
95Elfogadva17ms14644 KiB
96Elfogadva25ms16184 KiB
97Elfogadva24ms15964 KiB
98Elfogadva24ms15976 KiB
99Elfogadva24ms16084 KiB
100Elfogadva24ms15916 KiB
101Elfogadva25ms15688 KiB
102Elfogadva24ms15964 KiB
103Elfogadva24ms15892 KiB
104Elfogadva24ms15808 KiB
105Elfogadva23ms15692 KiB
106Elfogadva24ms15852 KiB
107Elfogadva24ms15912 KiB
108Elfogadva24ms15668 KiB
109Elfogadva24ms15904 KiB
110Elfogadva24ms15868 KiB
111Futási hiba412ms133736 KiB
112Futási hiba407ms133496 KiB
113Futási hiba409ms133636 KiB
114Futási hiba412ms133700 KiB
115Futási hiba409ms133352 KiB
116Futási hiba416ms133660 KiB
117Futási hiba421ms133740 KiB
118Futási hiba412ms133644 KiB
119Futási hiba418ms133616 KiB
120Futási hiba481ms133492 KiB
121Futási hiba412ms133600 KiB