108592024-04-17 08:32:0442Évzárópypy3Futási hiba 33/100264ms171692 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
1Elfogadva41ms77268 KiB
2Futási hiba264ms171692 KiB
subtask20/5
3Futási hiba202ms171528 KiB
4Futási hiba195ms171144 KiB
subtask30/7
5Futási hiba202ms171528 KiB
6Futási hiba195ms171144 KiB
7Futási hiba200ms170988 KiB
8Futási hiba195ms170660 KiB
9Futási hiba254ms170248 KiB
10Futási hiba173ms170084 KiB
subtask40/20
11Futási hiba229ms169868 KiB
12Futási hiba228ms169628 KiB
13Futási hiba226ms169208 KiB
14Futási hiba201ms168916 KiB
15Futási hiba195ms169128 KiB
16Futási hiba166ms169096 KiB
subtask513/13
17Elfogadva48ms80028 KiB
18Elfogadva46ms79744 KiB
19Elfogadva46ms80256 KiB
20Elfogadva48ms80384 KiB
21Elfogadva43ms80528 KiB
22Elfogadva46ms80732 KiB
23Elfogadva43ms80764 KiB
24Elfogadva50ms80632 KiB
25Elfogadva46ms81188 KiB
26Elfogadva46ms80824 KiB
27Elfogadva48ms81012 KiB
28Elfogadva43ms81112 KiB
29Elfogadva39ms81152 KiB
30Elfogadva41ms81648 KiB
31Elfogadva39ms81160 KiB
32Elfogadva41ms81420 KiB
33Elfogadva39ms81396 KiB
subtask620/20
34Elfogadva48ms80028 KiB
35Elfogadva46ms79744 KiB
36Elfogadva46ms80256 KiB
37Elfogadva48ms80384 KiB
38Elfogadva43ms80528 KiB
39Elfogadva46ms80732 KiB
40Elfogadva43ms80764 KiB
41Elfogadva50ms80632 KiB
42Elfogadva46ms81188 KiB
43Elfogadva46ms80824 KiB
44Elfogadva48ms81012 KiB
45Elfogadva43ms81112 KiB
46Elfogadva39ms81152 KiB
47Elfogadva41ms81648 KiB
48Elfogadva39ms81160 KiB
49Elfogadva41ms81420 KiB
50Elfogadva39ms81396 KiB
51Elfogadva75ms91752 KiB
52Elfogadva71ms92392 KiB
53Elfogadva67ms91624 KiB
54Elfogadva82ms91436 KiB
55Elfogadva70ms92308 KiB
56Elfogadva64ms91740 KiB
57Elfogadva64ms92000 KiB
58Elfogadva67ms92140 KiB
59Elfogadva65ms92168 KiB
60Elfogadva67ms92232 KiB
61Elfogadva64ms91768 KiB
62Elfogadva67ms92436 KiB
63Elfogadva68ms92044 KiB
64Elfogadva64ms91872 KiB
65Elfogadva68ms92412 KiB
subtask70/35
66Elfogadva48ms80028 KiB
67Futási hiba225ms168132 KiB
68Futási hiba202ms171528 KiB
69Futási hiba195ms171144 KiB
70Futási hiba200ms170988 KiB
71Futási hiba195ms170660 KiB
72Futási hiba254ms170248 KiB
73Futási hiba173ms170084 KiB
74Futási hiba229ms169868 KiB
75Futási hiba228ms169628 KiB
76Futási hiba226ms169208 KiB
77Futási hiba201ms168916 KiB
78Futási hiba195ms169128 KiB
79Futási hiba166ms169096 KiB
80Elfogadva46ms79744 KiB
81Elfogadva46ms80256 KiB
82Elfogadva48ms80384 KiB
83Elfogadva43ms80528 KiB
84Elfogadva46ms80732 KiB
85Elfogadva43ms80764 KiB
86Elfogadva50ms80632 KiB
87Elfogadva46ms81188 KiB
88Elfogadva46ms80824 KiB
89Elfogadva48ms81012 KiB
90Elfogadva43ms81112 KiB
91Elfogadva39ms81152 KiB
92Elfogadva41ms81648 KiB
93Elfogadva39ms81160 KiB
94Elfogadva41ms81420 KiB
95Elfogadva39ms81396 KiB
96Elfogadva75ms91752 KiB
97Elfogadva71ms92392 KiB
98Elfogadva67ms91624 KiB
99Elfogadva82ms91436 KiB
100Elfogadva70ms92308 KiB
101Elfogadva64ms91740 KiB
102Elfogadva64ms92000 KiB
103Elfogadva67ms92140 KiB
104Elfogadva65ms92168 KiB
105Elfogadva67ms92232 KiB
106Elfogadva64ms91768 KiB
107Elfogadva67ms92436 KiB
108Elfogadva68ms92044 KiB
109Elfogadva64ms91872 KiB
110Elfogadva68ms92412 KiB
111Futási hiba216ms167800 KiB
112Futási hiba188ms167696 KiB
113Futási hiba218ms167672 KiB
114Futási hiba204ms167704 KiB
115Futási hiba192ms167756 KiB
116Futási hiba238ms167976 KiB
117Futási hiba210ms167980 KiB
118Futási hiba215ms167480 KiB
119Futási hiba204ms167580 KiB
120Futási hiba246ms167712 KiB
121Futási hiba203ms167784 KiB