169382025-05-15 23:16:35Valaki2Évzárócpp17Accepted 100/100180ms24500 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int MAXN = 300'001;

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

bool phase_1;
bool xit;

void dfs(int cur, int col = 0) {
    while(ptr[cur] < g[cur].size()) {
        if(xit) {
            return;
        }
        int nei = g[cur][ptr[cur]].fi;
        int id = g[cur][ptr[cur]].se;
        if(del[id]) {
            ptr[cur]++;
            continue;
        }
        del[id] = true;
        ans[id] = col;
        deg[cur]++;
        deg[nei]++;
        ptr[cur]++;
        dfs(nei, 1 - col);
    }
    if(phase_1) {
        xit = true;
    }
}

void solve() {
    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);
    }

    phase_1 = true;

    for(int i = 0; i < 2 * n; i++) {
        if((g[i].size() - deg[i]) % 2 == 1) {
            xit = false;
            dfs(i);
        }
    }

    phase_1 = false;
    xit = false;

    for(int i = 0; i < 2 * n; i++) {
        dfs(i);
    }

    for (int i = 1; i <= n; i++) cout << (ans[i]?'F':'L');
    cout << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // int T; cin >> T; while(T--)
    solve();
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted7ms7476 KiB
2Accepted104ms18848 KiB
subtask25/5
3Accepted115ms17816 KiB
4Accepted116ms17768 KiB
subtask37/7
5Accepted115ms17816 KiB
6Accepted116ms17768 KiB
7Accepted120ms18080 KiB
8Accepted115ms18560 KiB
9Accepted137ms19040 KiB
10Accepted178ms20904 KiB
subtask420/20
11Accepted180ms23456 KiB
12Accepted153ms22220 KiB
13Accepted178ms22184 KiB
14Accepted153ms22364 KiB
15Accepted157ms22184 KiB
16Accepted145ms20896 KiB
subtask513/13
17Accepted8ms7672 KiB
18Accepted8ms7476 KiB
19Accepted7ms7476 KiB
20Accepted7ms7476 KiB
21Accepted7ms7476 KiB
22Accepted7ms7348 KiB
23Accepted8ms7476 KiB
24Accepted8ms7476 KiB
25Accepted7ms7372 KiB
26Accepted8ms7392 KiB
27Accepted7ms7276 KiB
28Accepted8ms7480 KiB
29Accepted8ms7476 KiB
30Accepted7ms7668 KiB
31Accepted7ms7476 KiB
32Accepted8ms7476 KiB
33Accepted7ms7452 KiB
subtask620/20
34Accepted8ms7672 KiB
35Accepted8ms7476 KiB
36Accepted7ms7476 KiB
37Accepted7ms7476 KiB
38Accepted7ms7476 KiB
39Accepted7ms7348 KiB
40Accepted8ms7476 KiB
41Accepted8ms7476 KiB
42Accepted7ms7372 KiB
43Accepted8ms7392 KiB
44Accepted7ms7276 KiB
45Accepted8ms7480 KiB
46Accepted8ms7476 KiB
47Accepted7ms7668 KiB
48Accepted7ms7476 KiB
49Accepted8ms7476 KiB
50Accepted7ms7452 KiB
51Accepted8ms7476 KiB
52Accepted8ms7476 KiB
53Accepted8ms7476 KiB
54Accepted7ms7488 KiB
55Accepted7ms7604 KiB
56Accepted8ms7560 KiB
57Accepted7ms7572 KiB
58Accepted8ms7476 KiB
59Accepted7ms7476 KiB
60Accepted7ms7500 KiB
61Accepted8ms7656 KiB
62Accepted8ms7484 KiB
63Accepted7ms7476 KiB
64Accepted7ms7476 KiB
65Accepted8ms7448 KiB
subtask735/35
66Accepted8ms7672 KiB
67Accepted101ms19064 KiB
68Accepted115ms17816 KiB
69Accepted116ms17768 KiB
70Accepted120ms18080 KiB
71Accepted115ms18560 KiB
72Accepted137ms19040 KiB
73Accepted178ms20904 KiB
74Accepted180ms23456 KiB
75Accepted153ms22220 KiB
76Accepted178ms22184 KiB
77Accepted153ms22364 KiB
78Accepted157ms22184 KiB
79Accepted145ms20896 KiB
80Accepted8ms7476 KiB
81Accepted7ms7476 KiB
82Accepted7ms7476 KiB
83Accepted7ms7476 KiB
84Accepted7ms7348 KiB
85Accepted8ms7476 KiB
86Accepted8ms7476 KiB
87Accepted7ms7372 KiB
88Accepted8ms7392 KiB
89Accepted7ms7276 KiB
90Accepted8ms7480 KiB
91Accepted8ms7476 KiB
92Accepted7ms7668 KiB
93Accepted7ms7476 KiB
94Accepted8ms7476 KiB
95Accepted7ms7452 KiB
96Accepted8ms7476 KiB
97Accepted8ms7476 KiB
98Accepted8ms7476 KiB
99Accepted7ms7488 KiB
100Accepted7ms7604 KiB
101Accepted8ms7560 KiB
102Accepted7ms7572 KiB
103Accepted8ms7476 KiB
104Accepted7ms7476 KiB
105Accepted7ms7500 KiB
106Accepted8ms7656 KiB
107Accepted8ms7484 KiB
108Accepted7ms7476 KiB
109Accepted7ms7476 KiB
110Accepted8ms7448 KiB
111Accepted87ms23544 KiB
112Accepted93ms24500 KiB
113Accepted92ms24340 KiB
114Accepted90ms24476 KiB
115Accepted94ms24476 KiB
116Accepted92ms24220 KiB
117Accepted101ms23444 KiB
118Accepted96ms24224 KiB
119Accepted94ms23448 KiB
120Accepted103ms21148 KiB
121Accepted90ms23968 KiB