169382025-05-15 23:16:35Valaki2Évzárócpp17Elfogadva 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();
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva7ms7476 KiB
2Elfogadva104ms18848 KiB
subtask25/5
3Elfogadva115ms17816 KiB
4Elfogadva116ms17768 KiB
subtask37/7
5Elfogadva115ms17816 KiB
6Elfogadva116ms17768 KiB
7Elfogadva120ms18080 KiB
8Elfogadva115ms18560 KiB
9Elfogadva137ms19040 KiB
10Elfogadva178ms20904 KiB
subtask420/20
11Elfogadva180ms23456 KiB
12Elfogadva153ms22220 KiB
13Elfogadva178ms22184 KiB
14Elfogadva153ms22364 KiB
15Elfogadva157ms22184 KiB
16Elfogadva145ms20896 KiB
subtask513/13
17Elfogadva8ms7672 KiB
18Elfogadva8ms7476 KiB
19Elfogadva7ms7476 KiB
20Elfogadva7ms7476 KiB
21Elfogadva7ms7476 KiB
22Elfogadva7ms7348 KiB
23Elfogadva8ms7476 KiB
24Elfogadva8ms7476 KiB
25Elfogadva7ms7372 KiB
26Elfogadva8ms7392 KiB
27Elfogadva7ms7276 KiB
28Elfogadva8ms7480 KiB
29Elfogadva8ms7476 KiB
30Elfogadva7ms7668 KiB
31Elfogadva7ms7476 KiB
32Elfogadva8ms7476 KiB
33Elfogadva7ms7452 KiB
subtask620/20
34Elfogadva8ms7672 KiB
35Elfogadva8ms7476 KiB
36Elfogadva7ms7476 KiB
37Elfogadva7ms7476 KiB
38Elfogadva7ms7476 KiB
39Elfogadva7ms7348 KiB
40Elfogadva8ms7476 KiB
41Elfogadva8ms7476 KiB
42Elfogadva7ms7372 KiB
43Elfogadva8ms7392 KiB
44Elfogadva7ms7276 KiB
45Elfogadva8ms7480 KiB
46Elfogadva8ms7476 KiB
47Elfogadva7ms7668 KiB
48Elfogadva7ms7476 KiB
49Elfogadva8ms7476 KiB
50Elfogadva7ms7452 KiB
51Elfogadva8ms7476 KiB
52Elfogadva8ms7476 KiB
53Elfogadva8ms7476 KiB
54Elfogadva7ms7488 KiB
55Elfogadva7ms7604 KiB
56Elfogadva8ms7560 KiB
57Elfogadva7ms7572 KiB
58Elfogadva8ms7476 KiB
59Elfogadva7ms7476 KiB
60Elfogadva7ms7500 KiB
61Elfogadva8ms7656 KiB
62Elfogadva8ms7484 KiB
63Elfogadva7ms7476 KiB
64Elfogadva7ms7476 KiB
65Elfogadva8ms7448 KiB
subtask735/35
66Elfogadva8ms7672 KiB
67Elfogadva101ms19064 KiB
68Elfogadva115ms17816 KiB
69Elfogadva116ms17768 KiB
70Elfogadva120ms18080 KiB
71Elfogadva115ms18560 KiB
72Elfogadva137ms19040 KiB
73Elfogadva178ms20904 KiB
74Elfogadva180ms23456 KiB
75Elfogadva153ms22220 KiB
76Elfogadva178ms22184 KiB
77Elfogadva153ms22364 KiB
78Elfogadva157ms22184 KiB
79Elfogadva145ms20896 KiB
80Elfogadva8ms7476 KiB
81Elfogadva7ms7476 KiB
82Elfogadva7ms7476 KiB
83Elfogadva7ms7476 KiB
84Elfogadva7ms7348 KiB
85Elfogadva8ms7476 KiB
86Elfogadva8ms7476 KiB
87Elfogadva7ms7372 KiB
88Elfogadva8ms7392 KiB
89Elfogadva7ms7276 KiB
90Elfogadva8ms7480 KiB
91Elfogadva8ms7476 KiB
92Elfogadva7ms7668 KiB
93Elfogadva7ms7476 KiB
94Elfogadva8ms7476 KiB
95Elfogadva7ms7452 KiB
96Elfogadva8ms7476 KiB
97Elfogadva8ms7476 KiB
98Elfogadva8ms7476 KiB
99Elfogadva7ms7488 KiB
100Elfogadva7ms7604 KiB
101Elfogadva8ms7560 KiB
102Elfogadva7ms7572 KiB
103Elfogadva8ms7476 KiB
104Elfogadva7ms7476 KiB
105Elfogadva7ms7500 KiB
106Elfogadva8ms7656 KiB
107Elfogadva8ms7484 KiB
108Elfogadva7ms7476 KiB
109Elfogadva7ms7476 KiB
110Elfogadva8ms7448 KiB
111Elfogadva87ms23544 KiB
112Elfogadva93ms24500 KiB
113Elfogadva92ms24340 KiB
114Elfogadva90ms24476 KiB
115Elfogadva94ms24476 KiB
116Elfogadva92ms24220 KiB
117Elfogadva101ms23444 KiB
118Elfogadva96ms24224 KiB
119Elfogadva94ms23448 KiB
120Elfogadva103ms21148 KiB
121Elfogadva90ms23968 KiB