108712024-04-17 10:52:26AblablablaÉvzárócpp17Accepted 100/100195ms29352 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

vector<vector<pii>> csucsok;
vector<bool> bejart;
vector<int> ans;

void dfs(int akt, int d){
    while(!csucsok[akt].empty()){
        pii kovi = csucsok[akt][csucsok[akt].size() - 1];
        csucsok[akt].pop_back();

        if(bejart[kovi.second]) continue;

        bejart[kovi.second] = 1;
        ans[kovi.second] = d;

        dfs(kovi.first, d ^ 1);
        return;
    }
}

int main(){
    int n;
    cin >> n;

    vector<pii> pontok(n);
    vector<int> pontX, pontY;
    for(int i = 0; i < n; i++){
        cin >> pontok[i].first >> pontok[i].second;

        pontX.push_back(pontok[i].first);
        pontY.push_back(pontok[i].second);
    }

    sort(pontX.begin(), pontX.end());
    sort(pontY.begin(), pontY.end());

    pontX.erase(unique(pontX.begin(), pontX.end()), pontX.end());
    pontY.erase(unique(pontY.begin(), pontY.end()), pontY.end());

    csucsok.assign(2 * n, vector<pii>());
    for(int i = 0; i < n; i++){
        pontok[i].first = lower_bound(pontX.begin(), pontX.end(), pontok[i].first) - pontX.begin();
        pontok[i].second = lower_bound(pontY.begin(), pontY.end(), pontok[i].second) - pontY.begin();
        pontok[i].second += n;

        csucsok[pontok[i].first].push_back({pontok[i].second, i});
        csucsok[pontok[i].second].push_back({pontok[i].first, i});
    }

    bejart.assign(n, 0);
    ans.assign(n, 0);

    for(int i = 0; i < n; i++){
        int d = 0;
        while(!csucsok[i].empty()){
            dfs(i, d);
            d ^=1;
        }
    }

    for(int i = 0; i < n; i++){
        cout << (ans[i] ? "F" : "L");
    }
    cout << "\n";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1812 KiB
2Accepted148ms20704 KiB
subtask25/5
3Accepted143ms23236 KiB
4Accepted144ms23452 KiB
subtask37/7
5Accepted143ms23236 KiB
6Accepted144ms23452 KiB
7Accepted156ms23932 KiB
8Accepted158ms24588 KiB
9Accepted173ms24768 KiB
10Accepted195ms28308 KiB
subtask420/20
11Accepted186ms22452 KiB
12Accepted182ms22664 KiB
13Accepted182ms22636 KiB
14Accepted178ms22860 KiB
15Accepted174ms23548 KiB
16Accepted181ms29352 KiB
subtask513/13
17Accepted3ms3764 KiB
18Accepted3ms3768 KiB
19Accepted2ms3764 KiB
20Accepted2ms3764 KiB
21Accepted2ms3768 KiB
22Accepted2ms3776 KiB
23Accepted2ms3692 KiB
24Accepted3ms3688 KiB
25Accepted3ms3940 KiB
26Accepted3ms3900 KiB
27Accepted3ms3908 KiB
28Accepted3ms3932 KiB
29Accepted3ms4020 KiB
30Accepted3ms3904 KiB
31Accepted3ms4148 KiB
32Accepted3ms4232 KiB
33Accepted3ms4116 KiB
subtask620/20
34Accepted3ms3764 KiB
35Accepted3ms3768 KiB
36Accepted2ms3764 KiB
37Accepted2ms3764 KiB
38Accepted2ms3768 KiB
39Accepted2ms3776 KiB
40Accepted2ms3692 KiB
41Accepted3ms3688 KiB
42Accepted3ms3940 KiB
43Accepted3ms3900 KiB
44Accepted3ms3908 KiB
45Accepted3ms3932 KiB
46Accepted3ms4020 KiB
47Accepted3ms3904 KiB
48Accepted3ms4148 KiB
49Accepted3ms4232 KiB
50Accepted3ms4116 KiB
51Accepted4ms4476 KiB
52Accepted4ms4436 KiB
53Accepted4ms4428 KiB
54Accepted4ms4432 KiB
55Accepted4ms4440 KiB
56Accepted4ms4436 KiB
57Accepted4ms4448 KiB
58Accepted4ms4460 KiB
59Accepted4ms4464 KiB
60Accepted4ms4484 KiB
61Accepted4ms4468 KiB
62Accepted4ms4468 KiB
63Accepted4ms4476 KiB
64Accepted4ms4460 KiB
65Accepted4ms4616 KiB
subtask735/35
66Accepted3ms3764 KiB
67Accepted148ms23056 KiB
68Accepted143ms23236 KiB
69Accepted144ms23452 KiB
70Accepted156ms23932 KiB
71Accepted158ms24588 KiB
72Accepted173ms24768 KiB
73Accepted195ms28308 KiB
74Accepted186ms22452 KiB
75Accepted182ms22664 KiB
76Accepted182ms22636 KiB
77Accepted178ms22860 KiB
78Accepted174ms23548 KiB
79Accepted181ms29352 KiB
80Accepted3ms3768 KiB
81Accepted2ms3764 KiB
82Accepted2ms3764 KiB
83Accepted2ms3768 KiB
84Accepted2ms3776 KiB
85Accepted2ms3692 KiB
86Accepted3ms3688 KiB
87Accepted3ms3940 KiB
88Accepted3ms3900 KiB
89Accepted3ms3908 KiB
90Accepted3ms3932 KiB
91Accepted3ms4020 KiB
92Accepted3ms3904 KiB
93Accepted3ms4148 KiB
94Accepted3ms4232 KiB
95Accepted3ms4116 KiB
96Accepted4ms4476 KiB
97Accepted4ms4436 KiB
98Accepted4ms4428 KiB
99Accepted4ms4432 KiB
100Accepted4ms4440 KiB
101Accepted4ms4436 KiB
102Accepted4ms4448 KiB
103Accepted4ms4460 KiB
104Accepted4ms4464 KiB
105Accepted4ms4484 KiB
106Accepted4ms4468 KiB
107Accepted4ms4468 KiB
108Accepted4ms4476 KiB
109Accepted4ms4460 KiB
110Accepted4ms4616 KiB
111Accepted136ms21624 KiB
112Accepted129ms22500 KiB
113Accepted129ms22496 KiB
114Accepted136ms22660 KiB
115Accepted134ms22664 KiB
116Accepted136ms22660 KiB
117Accepted140ms22016 KiB
118Accepted136ms22664 KiB
119Accepted140ms22796 KiB
120Accepted142ms22124 KiB
121Accepted138ms23184 KiB