109632024-04-21 14:13:16k_balintÉvzárócpp17Accepted 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";
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted17ms39480 KiB
2Accepted104ms61876 KiB
subtask25/5
3Accepted115ms71516 KiB
4Accepted130ms71760 KiB
subtask37/7
5Accepted115ms71516 KiB
6Accepted130ms71760 KiB
7Accepted127ms72288 KiB
8Accepted146ms72840 KiB
9Accepted158ms73600 KiB
10Accepted221ms84476 KiB
subtask420/20
11Accepted148ms60240 KiB
12Accepted145ms58372 KiB
13Accepted144ms58504 KiB
14Accepted143ms58860 KiB
15Accepted141ms58820 KiB
16Accepted186ms75904 KiB
subtask513/13
17Accepted19ms41676 KiB
18Accepted17ms41892 KiB
19Accepted19ms42104 KiB
20Accepted17ms42184 KiB
21Accepted16ms42188 KiB
22Accepted19ms42184 KiB
23Accepted17ms42412 KiB
24Accepted16ms42620 KiB
25Accepted16ms42612 KiB
26Accepted19ms42612 KiB
27Accepted19ms42396 KiB
28Accepted19ms42404 KiB
29Accepted17ms42396 KiB
30Accepted19ms42492 KiB
31Accepted19ms42496 KiB
32Accepted19ms42400 KiB
33Accepted19ms42408 KiB
subtask620/20
34Accepted19ms41676 KiB
35Accepted17ms41892 KiB
36Accepted19ms42104 KiB
37Accepted17ms42184 KiB
38Accepted16ms42188 KiB
39Accepted19ms42184 KiB
40Accepted17ms42412 KiB
41Accepted16ms42620 KiB
42Accepted16ms42612 KiB
43Accepted19ms42612 KiB
44Accepted19ms42396 KiB
45Accepted19ms42404 KiB
46Accepted17ms42396 KiB
47Accepted19ms42492 KiB
48Accepted19ms42496 KiB
49Accepted19ms42400 KiB
50Accepted19ms42408 KiB
51Accepted21ms42624 KiB
52Accepted18ms42616 KiB
53Accepted17ms42612 KiB
54Accepted20ms42504 KiB
55Accepted20ms42644 KiB
56Accepted20ms42740 KiB
57Accepted17ms42736 KiB
58Accepted17ms42740 KiB
59Accepted20ms42864 KiB
60Accepted20ms42860 KiB
61Accepted17ms42656 KiB
62Accepted20ms42752 KiB
63Accepted17ms42748 KiB
64Accepted17ms42656 KiB
65Accepted21ms42652 KiB
subtask735/35
66Accepted19ms41676 KiB
67Accepted104ms64620 KiB
68Accepted115ms71516 KiB
69Accepted130ms71760 KiB
70Accepted127ms72288 KiB
71Accepted146ms72840 KiB
72Accepted158ms73600 KiB
73Accepted221ms84476 KiB
74Accepted148ms60240 KiB
75Accepted145ms58372 KiB
76Accepted144ms58504 KiB
77Accepted143ms58860 KiB
78Accepted141ms58820 KiB
79Accepted186ms75904 KiB
80Accepted17ms41892 KiB
81Accepted19ms42104 KiB
82Accepted17ms42184 KiB
83Accepted16ms42188 KiB
84Accepted19ms42184 KiB
85Accepted17ms42412 KiB
86Accepted16ms42620 KiB
87Accepted16ms42612 KiB
88Accepted19ms42612 KiB
89Accepted19ms42396 KiB
90Accepted19ms42404 KiB
91Accepted17ms42396 KiB
92Accepted19ms42492 KiB
93Accepted19ms42496 KiB
94Accepted19ms42400 KiB
95Accepted19ms42408 KiB
96Accepted21ms42624 KiB
97Accepted18ms42616 KiB
98Accepted17ms42612 KiB
99Accepted20ms42504 KiB
100Accepted20ms42644 KiB
101Accepted20ms42740 KiB
102Accepted17ms42736 KiB
103Accepted17ms42740 KiB
104Accepted20ms42864 KiB
105Accepted20ms42860 KiB
106Accepted17ms42656 KiB
107Accepted20ms42752 KiB
108Accepted17ms42748 KiB
109Accepted17ms42656 KiB
110Accepted21ms42652 KiB
111Accepted97ms62604 KiB
112Accepted93ms63648 KiB
113Accepted93ms63608 KiB
114Accepted92ms64524 KiB
115Accepted97ms63936 KiB
116Accepted94ms64328 KiB
117Accepted97ms63184 KiB
118Accepted90ms63708 KiB
119Accepted96ms64264 KiB
120Accepted105ms63732 KiB
121Accepted93ms64340 KiB