107082024-04-10 09:43:50szilÉvzárócpp17Accepted 100/100153ms33988 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 300'001;

bool vis[MAXN];
int vx[MAXN], vy[MAXN];
vector<pair<int, int>> g[MAXN];
int ans[MAXN];

void dfs(int u, int d = 0) {
    while (!g[u].empty()) {
        auto [v, idx] = g[u].back();
        g[u].pop_back();
        if (vis[idx]) continue;
        vis[idx] = true;
        ans[idx] = d;
        dfs(v, d^1);
        return;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<int> comp1, comp2;
    for (int i = 1; i <= n; i++) {
        cin >> vx[i] >> vy[i];
        comp1.emplace_back(vx[i]);
        comp2.emplace_back(vy[i]);
    }
    sort(comp1.begin(), comp1.end());
    sort(comp2.begin(), comp2.end());
    comp1.erase(unique(comp1.begin(), comp1.end()), comp1.end());
    comp2.erase(unique(comp2.begin(), comp2.end()), comp2.end());
    for (int i = 1; i <= n; i++) {
        vx[i] = lower_bound(comp1.begin(), comp1.end(), vx[i])-comp1.begin();
        vy[i] = lower_bound(comp2.begin(), comp2.end(), vy[i])-comp2.begin(); 
        g[vx[i]].emplace_back(vy[i]+n, i);
        g[vy[i]+n].emplace_back(vx[i], i);
    }

    for (int i = 0; i < n; i++) {
        int d = 0;
        while (!g[i].empty()) {
            dfs(i, d);
            d^=1;
        }
    }
    
    for (int i = 1; i <= n; i++) cout << (ans[i]?'F':'L');
    cout << "\n";
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted8ms15912 KiB
2Accepted87ms25520 KiB
subtask25/5
3Accepted87ms28292 KiB
4Accepted90ms28504 KiB
subtask37/7
5Accepted87ms28292 KiB
6Accepted90ms28504 KiB
7Accepted93ms29140 KiB
8Accepted112ms29488 KiB
9Accepted109ms29908 KiB
10Accepted148ms33812 KiB
subtask420/20
11Accepted119ms27688 KiB
12Accepted127ms27660 KiB
13Accepted115ms27720 KiB
14Accepted131ms27668 KiB
15Accepted127ms28164 KiB
16Accepted153ms33988 KiB
subtask513/13
17Accepted8ms17348 KiB
18Accepted8ms17348 KiB
19Accepted8ms17348 KiB
20Accepted8ms17360 KiB
21Accepted8ms17680 KiB
22Accepted8ms17580 KiB
23Accepted8ms17728 KiB
24Accepted8ms17652 KiB
25Accepted8ms17660 KiB
26Accepted8ms17660 KiB
27Accepted8ms17724 KiB
28Accepted8ms17656 KiB
29Accepted8ms17660 KiB
30Accepted8ms17980 KiB
31Accepted8ms17944 KiB
32Accepted8ms17880 KiB
33Accepted8ms17880 KiB
subtask620/20
34Accepted8ms17348 KiB
35Accepted8ms17348 KiB
36Accepted8ms17348 KiB
37Accepted8ms17360 KiB
38Accepted8ms17680 KiB
39Accepted8ms17580 KiB
40Accepted8ms17728 KiB
41Accepted8ms17652 KiB
42Accepted8ms17660 KiB
43Accepted8ms17660 KiB
44Accepted8ms17724 KiB
45Accepted8ms17656 KiB
46Accepted8ms17660 KiB
47Accepted8ms17980 KiB
48Accepted8ms17944 KiB
49Accepted8ms17880 KiB
50Accepted8ms17880 KiB
51Accepted9ms17940 KiB
52Accepted9ms17936 KiB
53Accepted8ms18196 KiB
54Accepted9ms18276 KiB
55Accepted8ms18296 KiB
56Accepted8ms18284 KiB
57Accepted9ms18284 KiB
58Accepted8ms18284 KiB
59Accepted9ms18288 KiB
60Accepted8ms18292 KiB
61Accepted8ms18296 KiB
62Accepted9ms18288 KiB
63Accepted8ms18432 KiB
64Accepted9ms18284 KiB
65Accepted9ms18296 KiB
subtask735/35
66Accepted8ms17348 KiB
67Accepted87ms27776 KiB
68Accepted87ms28292 KiB
69Accepted90ms28504 KiB
70Accepted93ms29140 KiB
71Accepted112ms29488 KiB
72Accepted109ms29908 KiB
73Accepted148ms33812 KiB
74Accepted119ms27688 KiB
75Accepted127ms27660 KiB
76Accepted115ms27720 KiB
77Accepted131ms27668 KiB
78Accepted127ms28164 KiB
79Accepted153ms33988 KiB
80Accepted8ms17348 KiB
81Accepted8ms17348 KiB
82Accepted8ms17360 KiB
83Accepted8ms17680 KiB
84Accepted8ms17580 KiB
85Accepted8ms17728 KiB
86Accepted8ms17652 KiB
87Accepted8ms17660 KiB
88Accepted8ms17660 KiB
89Accepted8ms17724 KiB
90Accepted8ms17656 KiB
91Accepted8ms17660 KiB
92Accepted8ms17980 KiB
93Accepted8ms17944 KiB
94Accepted8ms17880 KiB
95Accepted8ms17880 KiB
96Accepted9ms17940 KiB
97Accepted9ms17936 KiB
98Accepted8ms18196 KiB
99Accepted9ms18276 KiB
100Accepted8ms18296 KiB
101Accepted8ms18284 KiB
102Accepted9ms18284 KiB
103Accepted8ms18284 KiB
104Accepted9ms18288 KiB
105Accepted8ms18292 KiB
106Accepted8ms18296 KiB
107Accepted9ms18288 KiB
108Accepted8ms18432 KiB
109Accepted9ms18284 KiB
110Accepted9ms18296 KiB
111Accepted76ms26824 KiB
112Accepted71ms28020 KiB
113Accepted75ms27988 KiB
114Accepted75ms28348 KiB
115Accepted78ms28192 KiB
116Accepted76ms28340 KiB
117Accepted82ms27520 KiB
118Accepted75ms28324 KiB
119Accepted79ms28604 KiB
120Accepted82ms27796 KiB
121Accepted76ms28728 KiB