// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int k = 2000000000;
vector<array<int , 3>> e;
vector<vector<array<int , 2>>> g;
vector<int> ans;
vector<int> a , q;
int u = 0;
int l = 0;
int n;
void dfs(int h){
while(!g[h].empty()){
if(ans[g[h].back()[1]] != -1){
g[h].pop_back();
continue;
}
int s = g[h].back()[1], d = g[h].back()[0];
ans[s] = 2;
dfs(g[h].back()[0]);
ans[s] = l;
if(q[d] != q[h])l = !l;
}
}
int32_t main() {
cin >> n;
ans.resize(n*2+3 , -1);
g.resize(n*2+3);
q.resize(n*2+3);
for(int i = 0; i < n;i++){
int y , z; cin >> y >> z;
a.push_back(y);
a.push_back(z+k);
e.push_back({y , z+k , u++});
}
sort(a.begin() , a.end());
a.erase(unique(a.begin(),a.end()),a.end());
for(int i = 0; i < n;i++){
e[i][0] = lower_bound(a.begin() , a.end() , e[i][0])-a.begin();
e[i][1] = lower_bound(a.begin() , a.end() , e[i][1])-a.begin();
q[e[i][0]] = 0;
q[e[i][1]] = 1;
g[e[i][0]].push_back({e[i][1] , e[i][2]});
g[e[i][1]].push_back({e[i][0] , e[i][2]});
}
int r = -1;
for(int i = 0; i < g.size();i++){
if(g[i].size()%2 == 1){
if(r == -1){
r = i;
continue;
}
g[i].push_back({r , u});
g[r].push_back({i , u++});
r = -1;
}
}
for(int i = 0; i < g.size();i++)if(g[i].size() != 0)dfs(i);
for(int i = 0; i < n;i++){
if(ans[i]){
cout << "L";
}else{
cout << "F";
}
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 1ms | 316 KiB | ||||
2 | Elfogadva | 166ms | 21992 KiB | ||||
subtask2 | 5/5 | ||||||
3 | Elfogadva | 189ms | 26408 KiB | ||||
4 | Elfogadva | 203ms | 26404 KiB | ||||
subtask3 | 7/7 | ||||||
5 | Elfogadva | 189ms | 26408 KiB | ||||
6 | Elfogadva | 203ms | 26404 KiB | ||||
7 | Elfogadva | 236ms | 26664 KiB | ||||
8 | Elfogadva | 214ms | 27176 KiB | ||||
9 | Elfogadva | 261ms | 27320 KiB | ||||
10 | Elfogadva | 284ms | 32292 KiB | ||||
subtask4 | 20/20 | ||||||
11 | Elfogadva | 217ms | 20516 KiB | ||||
12 | Elfogadva | 239ms | 19820 KiB | ||||
13 | Elfogadva | 215ms | 19752 KiB | ||||
14 | Elfogadva | 238ms | 19812 KiB | ||||
15 | Elfogadva | 222ms | 19856 KiB | ||||
16 | Elfogadva | 263ms | 28768 KiB | ||||
subtask5 | 13/13 | ||||||
17 | Elfogadva | 1ms | 500 KiB | ||||
18 | Elfogadva | 1ms | 508 KiB | ||||
19 | Elfogadva | 1ms | 316 KiB | ||||
20 | Elfogadva | 1ms | 316 KiB | ||||
21 | Elfogadva | 1ms | 316 KiB | ||||
22 | Elfogadva | 1ms | 316 KiB | ||||
23 | Elfogadva | 1ms | 316 KiB | ||||
24 | Elfogadva | 1ms | 316 KiB | ||||
25 | Elfogadva | 1ms | 316 KiB | ||||
26 | Elfogadva | 1ms | 316 KiB | ||||
27 | Elfogadva | 1ms | 316 KiB | ||||
28 | Elfogadva | 1ms | 316 KiB | ||||
29 | Elfogadva | 1ms | 316 KiB | ||||
30 | Elfogadva | 1ms | 316 KiB | ||||
31 | Elfogadva | 1ms | 316 KiB | ||||
32 | Elfogadva | 1ms | 316 KiB | ||||
33 | Elfogadva | 1ms | 316 KiB | ||||
subtask6 | 20/20 | ||||||
34 | Elfogadva | 1ms | 500 KiB | ||||
35 | Elfogadva | 1ms | 508 KiB | ||||
36 | Elfogadva | 1ms | 316 KiB | ||||
37 | Elfogadva | 1ms | 316 KiB | ||||
38 | Elfogadva | 1ms | 316 KiB | ||||
39 | Elfogadva | 1ms | 316 KiB | ||||
40 | Elfogadva | 1ms | 316 KiB | ||||
41 | Elfogadva | 1ms | 316 KiB | ||||
42 | Elfogadva | 1ms | 316 KiB | ||||
43 | Elfogadva | 1ms | 316 KiB | ||||
44 | Elfogadva | 1ms | 316 KiB | ||||
45 | Elfogadva | 1ms | 316 KiB | ||||
46 | Elfogadva | 1ms | 316 KiB | ||||
47 | Elfogadva | 1ms | 316 KiB | ||||
48 | Elfogadva | 1ms | 316 KiB | ||||
49 | Elfogadva | 1ms | 316 KiB | ||||
50 | Elfogadva | 1ms | 316 KiB | ||||
51 | Elfogadva | 2ms | 564 KiB | ||||
52 | Elfogadva | 2ms | 756 KiB | ||||
53 | Elfogadva | 2ms | 616 KiB | ||||
54 | Elfogadva | 2ms | 564 KiB | ||||
55 | Elfogadva | 2ms | 564 KiB | ||||
56 | Elfogadva | 2ms | 564 KiB | ||||
57 | Elfogadva | 2ms | 564 KiB | ||||
58 | Elfogadva | 2ms | 564 KiB | ||||
59 | Elfogadva | 2ms | 564 KiB | ||||
60 | Elfogadva | 2ms | 564 KiB | ||||
61 | Elfogadva | 2ms | 564 KiB | ||||
62 | Elfogadva | 2ms | 564 KiB | ||||
63 | Elfogadva | 3ms | 796 KiB | ||||
64 | Elfogadva | 2ms | 564 KiB | ||||
65 | Elfogadva | 2ms | 564 KiB | ||||
subtask7 | 35/35 | ||||||
66 | Elfogadva | 1ms | 500 KiB | ||||
67 | Elfogadva | 167ms | 22200 KiB | ||||
68 | Elfogadva | 189ms | 26408 KiB | ||||
69 | Elfogadva | 203ms | 26404 KiB | ||||
70 | Elfogadva | 236ms | 26664 KiB | ||||
71 | Elfogadva | 214ms | 27176 KiB | ||||
72 | Elfogadva | 261ms | 27320 KiB | ||||
73 | Elfogadva | 284ms | 32292 KiB | ||||
74 | Elfogadva | 217ms | 20516 KiB | ||||
75 | Elfogadva | 239ms | 19820 KiB | ||||
76 | Elfogadva | 215ms | 19752 KiB | ||||
77 | Elfogadva | 238ms | 19812 KiB | ||||
78 | Elfogadva | 222ms | 19856 KiB | ||||
79 | Elfogadva | 263ms | 28768 KiB | ||||
80 | Elfogadva | 1ms | 508 KiB | ||||
81 | Elfogadva | 1ms | 316 KiB | ||||
82 | Elfogadva | 1ms | 316 KiB | ||||
83 | Elfogadva | 1ms | 316 KiB | ||||
84 | Elfogadva | 1ms | 316 KiB | ||||
85 | Elfogadva | 1ms | 316 KiB | ||||
86 | Elfogadva | 1ms | 316 KiB | ||||
87 | Elfogadva | 1ms | 316 KiB | ||||
88 | Elfogadva | 1ms | 316 KiB | ||||
89 | Elfogadva | 1ms | 316 KiB | ||||
90 | Elfogadva | 1ms | 316 KiB | ||||
91 | Elfogadva | 1ms | 316 KiB | ||||
92 | Elfogadva | 1ms | 316 KiB | ||||
93 | Elfogadva | 1ms | 316 KiB | ||||
94 | Elfogadva | 1ms | 316 KiB | ||||
95 | Elfogadva | 1ms | 316 KiB | ||||
96 | Elfogadva | 2ms | 564 KiB | ||||
97 | Elfogadva | 2ms | 756 KiB | ||||
98 | Elfogadva | 2ms | 616 KiB | ||||
99 | Elfogadva | 2ms | 564 KiB | ||||
100 | Elfogadva | 2ms | 564 KiB | ||||
101 | Elfogadva | 2ms | 564 KiB | ||||
102 | Elfogadva | 2ms | 564 KiB | ||||
103 | Elfogadva | 2ms | 564 KiB | ||||
104 | Elfogadva | 2ms | 564 KiB | ||||
105 | Elfogadva | 2ms | 564 KiB | ||||
106 | Elfogadva | 2ms | 564 KiB | ||||
107 | Elfogadva | 2ms | 564 KiB | ||||
108 | Elfogadva | 3ms | 796 KiB | ||||
109 | Elfogadva | 2ms | 564 KiB | ||||
110 | Elfogadva | 2ms | 564 KiB | ||||
111 | Elfogadva | 155ms | 21016 KiB | ||||
112 | Elfogadva | 144ms | 21708 KiB | ||||
113 | Elfogadva | 150ms | 21560 KiB | ||||
114 | Elfogadva | 157ms | 21920 KiB | ||||
115 | Elfogadva | 150ms | 22056 KiB | ||||
116 | Elfogadva | 153ms | 22056 KiB | ||||
117 | Elfogadva | 162ms | 21280 KiB | ||||
118 | Elfogadva | 152ms | 22060 KiB | ||||
119 | Elfogadva | 157ms | 22312 KiB | ||||
120 | Elfogadva | 165ms | 21224 KiB | ||||
121 | Elfogadva | 158ms | 22032 KiB |