107082024-04-10 09:43:50szilÉvzárócpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva8ms15912 KiB
2Elfogadva87ms25520 KiB
subtask25/5
3Elfogadva87ms28292 KiB
4Elfogadva90ms28504 KiB
subtask37/7
5Elfogadva87ms28292 KiB
6Elfogadva90ms28504 KiB
7Elfogadva93ms29140 KiB
8Elfogadva112ms29488 KiB
9Elfogadva109ms29908 KiB
10Elfogadva148ms33812 KiB
subtask420/20
11Elfogadva119ms27688 KiB
12Elfogadva127ms27660 KiB
13Elfogadva115ms27720 KiB
14Elfogadva131ms27668 KiB
15Elfogadva127ms28164 KiB
16Elfogadva153ms33988 KiB
subtask513/13
17Elfogadva8ms17348 KiB
18Elfogadva8ms17348 KiB
19Elfogadva8ms17348 KiB
20Elfogadva8ms17360 KiB
21Elfogadva8ms17680 KiB
22Elfogadva8ms17580 KiB
23Elfogadva8ms17728 KiB
24Elfogadva8ms17652 KiB
25Elfogadva8ms17660 KiB
26Elfogadva8ms17660 KiB
27Elfogadva8ms17724 KiB
28Elfogadva8ms17656 KiB
29Elfogadva8ms17660 KiB
30Elfogadva8ms17980 KiB
31Elfogadva8ms17944 KiB
32Elfogadva8ms17880 KiB
33Elfogadva8ms17880 KiB
subtask620/20
34Elfogadva8ms17348 KiB
35Elfogadva8ms17348 KiB
36Elfogadva8ms17348 KiB
37Elfogadva8ms17360 KiB
38Elfogadva8ms17680 KiB
39Elfogadva8ms17580 KiB
40Elfogadva8ms17728 KiB
41Elfogadva8ms17652 KiB
42Elfogadva8ms17660 KiB
43Elfogadva8ms17660 KiB
44Elfogadva8ms17724 KiB
45Elfogadva8ms17656 KiB
46Elfogadva8ms17660 KiB
47Elfogadva8ms17980 KiB
48Elfogadva8ms17944 KiB
49Elfogadva8ms17880 KiB
50Elfogadva8ms17880 KiB
51Elfogadva9ms17940 KiB
52Elfogadva9ms17936 KiB
53Elfogadva8ms18196 KiB
54Elfogadva9ms18276 KiB
55Elfogadva8ms18296 KiB
56Elfogadva8ms18284 KiB
57Elfogadva9ms18284 KiB
58Elfogadva8ms18284 KiB
59Elfogadva9ms18288 KiB
60Elfogadva8ms18292 KiB
61Elfogadva8ms18296 KiB
62Elfogadva9ms18288 KiB
63Elfogadva8ms18432 KiB
64Elfogadva9ms18284 KiB
65Elfogadva9ms18296 KiB
subtask735/35
66Elfogadva8ms17348 KiB
67Elfogadva87ms27776 KiB
68Elfogadva87ms28292 KiB
69Elfogadva90ms28504 KiB
70Elfogadva93ms29140 KiB
71Elfogadva112ms29488 KiB
72Elfogadva109ms29908 KiB
73Elfogadva148ms33812 KiB
74Elfogadva119ms27688 KiB
75Elfogadva127ms27660 KiB
76Elfogadva115ms27720 KiB
77Elfogadva131ms27668 KiB
78Elfogadva127ms28164 KiB
79Elfogadva153ms33988 KiB
80Elfogadva8ms17348 KiB
81Elfogadva8ms17348 KiB
82Elfogadva8ms17360 KiB
83Elfogadva8ms17680 KiB
84Elfogadva8ms17580 KiB
85Elfogadva8ms17728 KiB
86Elfogadva8ms17652 KiB
87Elfogadva8ms17660 KiB
88Elfogadva8ms17660 KiB
89Elfogadva8ms17724 KiB
90Elfogadva8ms17656 KiB
91Elfogadva8ms17660 KiB
92Elfogadva8ms17980 KiB
93Elfogadva8ms17944 KiB
94Elfogadva8ms17880 KiB
95Elfogadva8ms17880 KiB
96Elfogadva9ms17940 KiB
97Elfogadva9ms17936 KiB
98Elfogadva8ms18196 KiB
99Elfogadva9ms18276 KiB
100Elfogadva8ms18296 KiB
101Elfogadva8ms18284 KiB
102Elfogadva9ms18284 KiB
103Elfogadva8ms18284 KiB
104Elfogadva9ms18288 KiB
105Elfogadva8ms18292 KiB
106Elfogadva8ms18296 KiB
107Elfogadva9ms18288 KiB
108Elfogadva8ms18432 KiB
109Elfogadva9ms18284 KiB
110Elfogadva9ms18296 KiB
111Elfogadva76ms26824 KiB
112Elfogadva71ms28020 KiB
113Elfogadva75ms27988 KiB
114Elfogadva75ms28348 KiB
115Elfogadva78ms28192 KiB
116Elfogadva76ms28340 KiB
117Elfogadva82ms27520 KiB
118Elfogadva75ms28324 KiB
119Elfogadva79ms28604 KiB
120Elfogadva82ms27796 KiB
121Elfogadva76ms28728 KiB