10708 2024. 04. 10 09:43:50 szil Évzáró cpp17 Elfogadva 100/100 153ms 33988 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 8ms 15912 KiB
2 Elfogadva 87ms 25520 KiB
subtask2 5/5
3 Elfogadva 87ms 28292 KiB
4 Elfogadva 90ms 28504 KiB
subtask3 7/7
5 Elfogadva 87ms 28292 KiB
6 Elfogadva 90ms 28504 KiB
7 Elfogadva 93ms 29140 KiB
8 Elfogadva 112ms 29488 KiB
9 Elfogadva 109ms 29908 KiB
10 Elfogadva 148ms 33812 KiB
subtask4 20/20
11 Elfogadva 119ms 27688 KiB
12 Elfogadva 127ms 27660 KiB
13 Elfogadva 115ms 27720 KiB
14 Elfogadva 131ms 27668 KiB
15 Elfogadva 127ms 28164 KiB
16 Elfogadva 153ms 33988 KiB
subtask5 13/13
17 Elfogadva 8ms 17348 KiB
18 Elfogadva 8ms 17348 KiB
19 Elfogadva 8ms 17348 KiB
20 Elfogadva 8ms 17360 KiB
21 Elfogadva 8ms 17680 KiB
22 Elfogadva 8ms 17580 KiB
23 Elfogadva 8ms 17728 KiB
24 Elfogadva 8ms 17652 KiB
25 Elfogadva 8ms 17660 KiB
26 Elfogadva 8ms 17660 KiB
27 Elfogadva 8ms 17724 KiB
28 Elfogadva 8ms 17656 KiB
29 Elfogadva 8ms 17660 KiB
30 Elfogadva 8ms 17980 KiB
31 Elfogadva 8ms 17944 KiB
32 Elfogadva 8ms 17880 KiB
33 Elfogadva 8ms 17880 KiB
subtask6 20/20
34 Elfogadva 8ms 17348 KiB
35 Elfogadva 8ms 17348 KiB
36 Elfogadva 8ms 17348 KiB
37 Elfogadva 8ms 17360 KiB
38 Elfogadva 8ms 17680 KiB
39 Elfogadva 8ms 17580 KiB
40 Elfogadva 8ms 17728 KiB
41 Elfogadva 8ms 17652 KiB
42 Elfogadva 8ms 17660 KiB
43 Elfogadva 8ms 17660 KiB
44 Elfogadva 8ms 17724 KiB
45 Elfogadva 8ms 17656 KiB
46 Elfogadva 8ms 17660 KiB
47 Elfogadva 8ms 17980 KiB
48 Elfogadva 8ms 17944 KiB
49 Elfogadva 8ms 17880 KiB
50 Elfogadva 8ms 17880 KiB
51 Elfogadva 9ms 17940 KiB
52 Elfogadva 9ms 17936 KiB
53 Elfogadva 8ms 18196 KiB
54 Elfogadva 9ms 18276 KiB
55 Elfogadva 8ms 18296 KiB
56 Elfogadva 8ms 18284 KiB
57 Elfogadva 9ms 18284 KiB
58 Elfogadva 8ms 18284 KiB
59 Elfogadva 9ms 18288 KiB
60 Elfogadva 8ms 18292 KiB
61 Elfogadva 8ms 18296 KiB
62 Elfogadva 9ms 18288 KiB
63 Elfogadva 8ms 18432 KiB
64 Elfogadva 9ms 18284 KiB
65 Elfogadva 9ms 18296 KiB
subtask7 35/35
66 Elfogadva 8ms 17348 KiB
67 Elfogadva 87ms 27776 KiB
68 Elfogadva 87ms 28292 KiB
69 Elfogadva 90ms 28504 KiB
70 Elfogadva 93ms 29140 KiB
71 Elfogadva 112ms 29488 KiB
72 Elfogadva 109ms 29908 KiB
73 Elfogadva 148ms 33812 KiB
74 Elfogadva 119ms 27688 KiB
75 Elfogadva 127ms 27660 KiB
76 Elfogadva 115ms 27720 KiB
77 Elfogadva 131ms 27668 KiB
78 Elfogadva 127ms 28164 KiB
79 Elfogadva 153ms 33988 KiB
80 Elfogadva 8ms 17348 KiB
81 Elfogadva 8ms 17348 KiB
82 Elfogadva 8ms 17360 KiB
83 Elfogadva 8ms 17680 KiB
84 Elfogadva 8ms 17580 KiB
85 Elfogadva 8ms 17728 KiB
86 Elfogadva 8ms 17652 KiB
87 Elfogadva 8ms 17660 KiB
88 Elfogadva 8ms 17660 KiB
89 Elfogadva 8ms 17724 KiB
90 Elfogadva 8ms 17656 KiB
91 Elfogadva 8ms 17660 KiB
92 Elfogadva 8ms 17980 KiB
93 Elfogadva 8ms 17944 KiB
94 Elfogadva 8ms 17880 KiB
95 Elfogadva 8ms 17880 KiB
96 Elfogadva 9ms 17940 KiB
97 Elfogadva 9ms 17936 KiB
98 Elfogadva 8ms 18196 KiB
99 Elfogadva 9ms 18276 KiB
100 Elfogadva 8ms 18296 KiB
101 Elfogadva 8ms 18284 KiB
102 Elfogadva 9ms 18284 KiB
103 Elfogadva 8ms 18284 KiB
104 Elfogadva 9ms 18288 KiB
105 Elfogadva 8ms 18292 KiB
106 Elfogadva 8ms 18296 KiB
107 Elfogadva 9ms 18288 KiB
108 Elfogadva 8ms 18432 KiB
109 Elfogadva 9ms 18284 KiB
110 Elfogadva 9ms 18296 KiB
111 Elfogadva 76ms 26824 KiB
112 Elfogadva 71ms 28020 KiB
113 Elfogadva 75ms 27988 KiB
114 Elfogadva 75ms 28348 KiB
115 Elfogadva 78ms 28192 KiB
116 Elfogadva 76ms 28340 KiB
117 Elfogadva 82ms 27520 KiB
118 Elfogadva 75ms 28324 KiB
119 Elfogadva 79ms 28604 KiB
120 Elfogadva 82ms 27796 KiB
121 Elfogadva 76ms 28728 KiB