109632024-04-21 14:13:16k_balintÉvzárócpp17Elfogadva 100/100221ms84476 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=8e5+5;

vector<int> compx;
vector<int> compy;

int fx(int k){
    return lower_bound(compx.begin(),compx.end(),k)-compx.begin() + 1;
}

int fy(int k){
    return lower_bound(compy.begin(),compy.end(),k)-compy.begin() + 1 + compx.size();
}

int n,N;
vector<pair<int,int>> adj[c];
bool volt[c];
int idx[c];
bool ans[c], vis[c], deg[c];
vector<pair<int,int>> edg;

void dfs(int v){
    vis[v]=1;
    while(idx[v]<adj[v].size()){
        int x=idx[v];
        int id=adj[v][x].second;
        if(volt[id]){
            ++idx[v];
            continue;
        }
        volt[id]=1;
        ++idx[v];
        if(v<=compx.size()) ans[id]=1;
        else ans[id]=0;
        dfs(adj[v][x].first);
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        int a,b; cin>>a>>b;
        edg.push_back(make_pair(a,b));
        compx.push_back(a);
        compy.push_back(b);
    }

    sort(compx.begin(),compx.end());
    compx.resize(unique(compx.begin(),compx.end())-compx.begin());

    sort(compy.begin(),compy.end());
    compy.resize(unique(compy.begin(),compy.end())-compy.begin());

    N=compx.size()+compy.size();

    for(int i=0;i<n;i++){
        int a=fx(edg[i].first);
        int b=fy(edg[i].second);
        adj[a].push_back(make_pair(b,i));
        adj[b].push_back(make_pair(a,i));
        deg[a]^=1; deg[b]^=1;
    }

    int m=n;
    int p=-1;
    for(int i=1;i<=N;i++){
        if(deg[i]){
            if(p==-1) p=i;
            else{
                adj[i].push_back(make_pair(p,m));
                adj[p].push_back(make_pair(i,m++));
                p=-1;
            }
        }
    }

    for(int i=1;i<=N;i++){
        if(!vis[i]) dfs(i);
    }

    for(int i=0;i<n;i++){
        if(ans[i]) cout << "L";
        else cout << "F";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva17ms39480 KiB
2Elfogadva104ms61876 KiB
subtask25/5
3Elfogadva115ms71516 KiB
4Elfogadva130ms71760 KiB
subtask37/7
5Elfogadva115ms71516 KiB
6Elfogadva130ms71760 KiB
7Elfogadva127ms72288 KiB
8Elfogadva146ms72840 KiB
9Elfogadva158ms73600 KiB
10Elfogadva221ms84476 KiB
subtask420/20
11Elfogadva148ms60240 KiB
12Elfogadva145ms58372 KiB
13Elfogadva144ms58504 KiB
14Elfogadva143ms58860 KiB
15Elfogadva141ms58820 KiB
16Elfogadva186ms75904 KiB
subtask513/13
17Elfogadva19ms41676 KiB
18Elfogadva17ms41892 KiB
19Elfogadva19ms42104 KiB
20Elfogadva17ms42184 KiB
21Elfogadva16ms42188 KiB
22Elfogadva19ms42184 KiB
23Elfogadva17ms42412 KiB
24Elfogadva16ms42620 KiB
25Elfogadva16ms42612 KiB
26Elfogadva19ms42612 KiB
27Elfogadva19ms42396 KiB
28Elfogadva19ms42404 KiB
29Elfogadva17ms42396 KiB
30Elfogadva19ms42492 KiB
31Elfogadva19ms42496 KiB
32Elfogadva19ms42400 KiB
33Elfogadva19ms42408 KiB
subtask620/20
34Elfogadva19ms41676 KiB
35Elfogadva17ms41892 KiB
36Elfogadva19ms42104 KiB
37Elfogadva17ms42184 KiB
38Elfogadva16ms42188 KiB
39Elfogadva19ms42184 KiB
40Elfogadva17ms42412 KiB
41Elfogadva16ms42620 KiB
42Elfogadva16ms42612 KiB
43Elfogadva19ms42612 KiB
44Elfogadva19ms42396 KiB
45Elfogadva19ms42404 KiB
46Elfogadva17ms42396 KiB
47Elfogadva19ms42492 KiB
48Elfogadva19ms42496 KiB
49Elfogadva19ms42400 KiB
50Elfogadva19ms42408 KiB
51Elfogadva21ms42624 KiB
52Elfogadva18ms42616 KiB
53Elfogadva17ms42612 KiB
54Elfogadva20ms42504 KiB
55Elfogadva20ms42644 KiB
56Elfogadva20ms42740 KiB
57Elfogadva17ms42736 KiB
58Elfogadva17ms42740 KiB
59Elfogadva20ms42864 KiB
60Elfogadva20ms42860 KiB
61Elfogadva17ms42656 KiB
62Elfogadva20ms42752 KiB
63Elfogadva17ms42748 KiB
64Elfogadva17ms42656 KiB
65Elfogadva21ms42652 KiB
subtask735/35
66Elfogadva19ms41676 KiB
67Elfogadva104ms64620 KiB
68Elfogadva115ms71516 KiB
69Elfogadva130ms71760 KiB
70Elfogadva127ms72288 KiB
71Elfogadva146ms72840 KiB
72Elfogadva158ms73600 KiB
73Elfogadva221ms84476 KiB
74Elfogadva148ms60240 KiB
75Elfogadva145ms58372 KiB
76Elfogadva144ms58504 KiB
77Elfogadva143ms58860 KiB
78Elfogadva141ms58820 KiB
79Elfogadva186ms75904 KiB
80Elfogadva17ms41892 KiB
81Elfogadva19ms42104 KiB
82Elfogadva17ms42184 KiB
83Elfogadva16ms42188 KiB
84Elfogadva19ms42184 KiB
85Elfogadva17ms42412 KiB
86Elfogadva16ms42620 KiB
87Elfogadva16ms42612 KiB
88Elfogadva19ms42612 KiB
89Elfogadva19ms42396 KiB
90Elfogadva19ms42404 KiB
91Elfogadva17ms42396 KiB
92Elfogadva19ms42492 KiB
93Elfogadva19ms42496 KiB
94Elfogadva19ms42400 KiB
95Elfogadva19ms42408 KiB
96Elfogadva21ms42624 KiB
97Elfogadva18ms42616 KiB
98Elfogadva17ms42612 KiB
99Elfogadva20ms42504 KiB
100Elfogadva20ms42644 KiB
101Elfogadva20ms42740 KiB
102Elfogadva17ms42736 KiB
103Elfogadva17ms42740 KiB
104Elfogadva20ms42864 KiB
105Elfogadva20ms42860 KiB
106Elfogadva17ms42656 KiB
107Elfogadva20ms42752 KiB
108Elfogadva17ms42748 KiB
109Elfogadva17ms42656 KiB
110Elfogadva21ms42652 KiB
111Elfogadva97ms62604 KiB
112Elfogadva93ms63648 KiB
113Elfogadva93ms63608 KiB
114Elfogadva92ms64524 KiB
115Elfogadva97ms63936 KiB
116Elfogadva94ms64328 KiB
117Elfogadva97ms63184 KiB
118Elfogadva90ms63708 KiB
119Elfogadva96ms64264 KiB
120Elfogadva105ms63732 KiB
121Elfogadva93ms64340 KiB