169372025-05-15 23:06:52Valaki2Évzárócpp17Wrong answer 12/100179ms24484 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;

    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
1Accepted8ms7476 KiB
2Accepted96ms18848 KiB
subtask25/5
3Accepted93ms17816 KiB
4Accepted104ms17764 KiB
subtask37/7
5Accepted93ms17816 KiB
6Accepted104ms17764 KiB
7Accepted118ms18028 KiB
8Accepted115ms18592 KiB
9Accepted145ms18572 KiB
10Accepted150ms20804 KiB
subtask40/20
11Wrong answer138ms20988 KiB
12Wrong answer155ms18952 KiB
13Wrong answer148ms18452 KiB
14Wrong answer152ms18340 KiB
15Wrong answer127ms18588 KiB
16Accepted179ms20908 KiB
subtask50/13
17Accepted8ms7476 KiB
18Accepted7ms7476 KiB
19Accepted7ms7476 KiB
20Accepted8ms7476 KiB
21Accepted7ms7444 KiB
22Accepted7ms7480 KiB
23Accepted8ms7336 KiB
24Wrong answer8ms7476 KiB
25Wrong answer8ms7504 KiB
26Wrong answer7ms7516 KiB
27Accepted8ms7504 KiB
28Accepted6ms7508 KiB
29Accepted7ms7372 KiB
30Accepted7ms7504 KiB
31Accepted8ms7312 KiB
32Accepted8ms7476 KiB
33Accepted7ms7528 KiB
subtask60/20
34Accepted8ms7476 KiB
35Accepted7ms7476 KiB
36Accepted7ms7476 KiB
37Accepted8ms7476 KiB
38Accepted7ms7444 KiB
39Accepted7ms7480 KiB
40Accepted8ms7336 KiB
41Wrong answer8ms7476 KiB
42Wrong answer8ms7504 KiB
43Wrong answer7ms7516 KiB
44Accepted8ms7504 KiB
45Accepted6ms7508 KiB
46Accepted7ms7372 KiB
47Accepted7ms7504 KiB
48Accepted8ms7312 KiB
49Accepted8ms7476 KiB
50Accepted7ms7528 KiB
51Wrong answer7ms7568 KiB
52Wrong answer8ms7616 KiB
53Wrong answer7ms7528 KiB
54Wrong answer8ms7476 KiB
55Accepted7ms7560 KiB
56Accepted8ms7604 KiB
57Accepted7ms7660 KiB
58Accepted8ms7692 KiB
59Accepted8ms7488 KiB
60Accepted8ms7476 KiB
61Accepted8ms7476 KiB
62Accepted8ms7476 KiB
63Wrong answer8ms7480 KiB
64Accepted8ms7644 KiB
65Accepted8ms7476 KiB
subtask70/35
66Accepted8ms7476 KiB
67Accepted98ms18976 KiB
68Accepted93ms17816 KiB
69Accepted104ms17764 KiB
70Accepted118ms18028 KiB
71Accepted115ms18592 KiB
72Accepted145ms18572 KiB
73Accepted150ms20804 KiB
74Wrong answer138ms20988 KiB
75Wrong answer155ms18952 KiB
76Wrong answer148ms18452 KiB
77Wrong answer152ms18340 KiB
78Wrong answer127ms18588 KiB
79Accepted179ms20908 KiB
80Accepted7ms7476 KiB
81Accepted7ms7476 KiB
82Accepted8ms7476 KiB
83Accepted7ms7444 KiB
84Accepted7ms7480 KiB
85Accepted8ms7336 KiB
86Wrong answer8ms7476 KiB
87Wrong answer8ms7504 KiB
88Wrong answer7ms7516 KiB
89Accepted8ms7504 KiB
90Accepted6ms7508 KiB
91Accepted7ms7372 KiB
92Accepted7ms7504 KiB
93Accepted8ms7312 KiB
94Accepted8ms7476 KiB
95Accepted7ms7528 KiB
96Wrong answer7ms7568 KiB
97Wrong answer8ms7616 KiB
98Wrong answer7ms7528 KiB
99Wrong answer8ms7476 KiB
100Accepted7ms7560 KiB
101Accepted8ms7604 KiB
102Accepted7ms7660 KiB
103Accepted8ms7692 KiB
104Accepted8ms7488 KiB
105Accepted8ms7476 KiB
106Accepted8ms7476 KiB
107Accepted8ms7476 KiB
108Wrong answer8ms7480 KiB
109Accepted8ms7644 KiB
110Accepted8ms7476 KiB
111Accepted93ms23544 KiB
112Accepted90ms24352 KiB
113Accepted90ms24376 KiB
114Accepted93ms24476 KiB
115Accepted89ms24484 KiB
116Accepted97ms24220 KiB
117Accepted93ms23344 KiB
118Accepted89ms24008 KiB
119Wrong answer93ms23336 KiB
120Wrong answer101ms21148 KiB
121Wrong answer94ms23964 KiB