169372025-05-15 23:06:52Valaki2Évzárócpp17Hibás válasz 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();
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva8ms7476 KiB
2Elfogadva96ms18848 KiB
subtask25/5
3Elfogadva93ms17816 KiB
4Elfogadva104ms17764 KiB
subtask37/7
5Elfogadva93ms17816 KiB
6Elfogadva104ms17764 KiB
7Elfogadva118ms18028 KiB
8Elfogadva115ms18592 KiB
9Elfogadva145ms18572 KiB
10Elfogadva150ms20804 KiB
subtask40/20
11Hibás válasz138ms20988 KiB
12Hibás válasz155ms18952 KiB
13Hibás válasz148ms18452 KiB
14Hibás válasz152ms18340 KiB
15Hibás válasz127ms18588 KiB
16Elfogadva179ms20908 KiB
subtask50/13
17Elfogadva8ms7476 KiB
18Elfogadva7ms7476 KiB
19Elfogadva7ms7476 KiB
20Elfogadva8ms7476 KiB
21Elfogadva7ms7444 KiB
22Elfogadva7ms7480 KiB
23Elfogadva8ms7336 KiB
24Hibás válasz8ms7476 KiB
25Hibás válasz8ms7504 KiB
26Hibás válasz7ms7516 KiB
27Elfogadva8ms7504 KiB
28Elfogadva6ms7508 KiB
29Elfogadva7ms7372 KiB
30Elfogadva7ms7504 KiB
31Elfogadva8ms7312 KiB
32Elfogadva8ms7476 KiB
33Elfogadva7ms7528 KiB
subtask60/20
34Elfogadva8ms7476 KiB
35Elfogadva7ms7476 KiB
36Elfogadva7ms7476 KiB
37Elfogadva8ms7476 KiB
38Elfogadva7ms7444 KiB
39Elfogadva7ms7480 KiB
40Elfogadva8ms7336 KiB
41Hibás válasz8ms7476 KiB
42Hibás válasz8ms7504 KiB
43Hibás válasz7ms7516 KiB
44Elfogadva8ms7504 KiB
45Elfogadva6ms7508 KiB
46Elfogadva7ms7372 KiB
47Elfogadva7ms7504 KiB
48Elfogadva8ms7312 KiB
49Elfogadva8ms7476 KiB
50Elfogadva7ms7528 KiB
51Hibás válasz7ms7568 KiB
52Hibás válasz8ms7616 KiB
53Hibás válasz7ms7528 KiB
54Hibás válasz8ms7476 KiB
55Elfogadva7ms7560 KiB
56Elfogadva8ms7604 KiB
57Elfogadva7ms7660 KiB
58Elfogadva8ms7692 KiB
59Elfogadva8ms7488 KiB
60Elfogadva8ms7476 KiB
61Elfogadva8ms7476 KiB
62Elfogadva8ms7476 KiB
63Hibás válasz8ms7480 KiB
64Elfogadva8ms7644 KiB
65Elfogadva8ms7476 KiB
subtask70/35
66Elfogadva8ms7476 KiB
67Elfogadva98ms18976 KiB
68Elfogadva93ms17816 KiB
69Elfogadva104ms17764 KiB
70Elfogadva118ms18028 KiB
71Elfogadva115ms18592 KiB
72Elfogadva145ms18572 KiB
73Elfogadva150ms20804 KiB
74Hibás válasz138ms20988 KiB
75Hibás válasz155ms18952 KiB
76Hibás válasz148ms18452 KiB
77Hibás válasz152ms18340 KiB
78Hibás válasz127ms18588 KiB
79Elfogadva179ms20908 KiB
80Elfogadva7ms7476 KiB
81Elfogadva7ms7476 KiB
82Elfogadva8ms7476 KiB
83Elfogadva7ms7444 KiB
84Elfogadva7ms7480 KiB
85Elfogadva8ms7336 KiB
86Hibás válasz8ms7476 KiB
87Hibás válasz8ms7504 KiB
88Hibás válasz7ms7516 KiB
89Elfogadva8ms7504 KiB
90Elfogadva6ms7508 KiB
91Elfogadva7ms7372 KiB
92Elfogadva7ms7504 KiB
93Elfogadva8ms7312 KiB
94Elfogadva8ms7476 KiB
95Elfogadva7ms7528 KiB
96Hibás válasz7ms7568 KiB
97Hibás válasz8ms7616 KiB
98Hibás válasz7ms7528 KiB
99Hibás válasz8ms7476 KiB
100Elfogadva7ms7560 KiB
101Elfogadva8ms7604 KiB
102Elfogadva7ms7660 KiB
103Elfogadva8ms7692 KiB
104Elfogadva8ms7488 KiB
105Elfogadva8ms7476 KiB
106Elfogadva8ms7476 KiB
107Elfogadva8ms7476 KiB
108Hibás válasz8ms7480 KiB
109Elfogadva8ms7644 KiB
110Elfogadva8ms7476 KiB
111Elfogadva93ms23544 KiB
112Elfogadva90ms24352 KiB
113Elfogadva90ms24376 KiB
114Elfogadva93ms24476 KiB
115Elfogadva89ms24484 KiB
116Elfogadva97ms24220 KiB
117Elfogadva93ms23344 KiB
118Elfogadva89ms24008 KiB
119Hibás válasz93ms23336 KiB
120Hibás válasz101ms21148 KiB
121Hibás válasz94ms23964 KiB