109622024-04-21 14:04:39k_balintÉvzárócpp17Wrong answer 32/100203ms101556 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++));
            }
        }
    }

    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
1Accepted20ms39480 KiB
2Wrong answer111ms62404 KiB
subtask25/5
3Accepted136ms79924 KiB
4Accepted137ms80224 KiB
subtask37/7
5Accepted136ms79924 KiB
6Accepted137ms80224 KiB
7Accepted149ms80812 KiB
8Accepted155ms81216 KiB
9Accepted170ms82044 KiB
10Accepted203ms100908 KiB
subtask420/20
11Accepted148ms59904 KiB
12Accepted146ms57960 KiB
13Accepted138ms57820 KiB
14Accepted136ms58200 KiB
15Accepted141ms58888 KiB
16Accepted197ms101556 KiB
subtask50/13
17Accepted17ms41368 KiB
18Accepted17ms41580 KiB
19Accepted20ms41664 KiB
20Accepted20ms41664 KiB
21Accepted19ms41664 KiB
22Accepted19ms41792 KiB
23Accepted19ms41760 KiB
24Accepted17ms41984 KiB
25Accepted19ms41972 KiB
26Accepted19ms41980 KiB
27Accepted19ms42064 KiB
28Accepted19ms41972 KiB
29Accepted19ms42088 KiB
30Accepted19ms42212 KiB
31Wrong answer19ms42188 KiB
32Wrong answer19ms42332 KiB
33Wrong answer19ms42256 KiB
subtask60/20
34Accepted17ms41368 KiB
35Accepted17ms41580 KiB
36Accepted20ms41664 KiB
37Accepted20ms41664 KiB
38Accepted19ms41664 KiB
39Accepted19ms41792 KiB
40Accepted19ms41760 KiB
41Accepted17ms41984 KiB
42Accepted19ms41972 KiB
43Accepted19ms41980 KiB
44Accepted19ms42064 KiB
45Accepted19ms41972 KiB
46Accepted19ms42088 KiB
47Accepted19ms42212 KiB
48Wrong answer19ms42188 KiB
49Wrong answer19ms42332 KiB
50Wrong answer19ms42256 KiB
51Accepted20ms42484 KiB
52Accepted20ms42348 KiB
53Accepted20ms42352 KiB
54Accepted20ms42480 KiB
55Wrong answer20ms42620 KiB
56Wrong answer20ms42496 KiB
57Accepted20ms42516 KiB
58Wrong answer20ms42508 KiB
59Wrong answer20ms42508 KiB
60Wrong answer20ms42744 KiB
61Accepted20ms42732 KiB
62Wrong answer20ms42776 KiB
63Wrong answer18ms42876 KiB
64Wrong answer17ms42896 KiB
65Wrong answer20ms42880 KiB
subtask70/35
66Accepted17ms41368 KiB
67Wrong answer111ms65244 KiB
68Accepted136ms79924 KiB
69Accepted137ms80224 KiB
70Accepted149ms80812 KiB
71Accepted155ms81216 KiB
72Accepted170ms82044 KiB
73Accepted203ms100908 KiB
74Accepted148ms59904 KiB
75Accepted146ms57960 KiB
76Accepted138ms57820 KiB
77Accepted136ms58200 KiB
78Accepted141ms58888 KiB
79Accepted197ms101556 KiB
80Accepted17ms41580 KiB
81Accepted20ms41664 KiB
82Accepted20ms41664 KiB
83Accepted19ms41664 KiB
84Accepted19ms41792 KiB
85Accepted19ms41760 KiB
86Accepted17ms41984 KiB
87Accepted19ms41972 KiB
88Accepted19ms41980 KiB
89Accepted19ms42064 KiB
90Accepted19ms41972 KiB
91Accepted19ms42088 KiB
92Accepted19ms42212 KiB
93Wrong answer19ms42188 KiB
94Wrong answer19ms42332 KiB
95Wrong answer19ms42256 KiB
96Accepted20ms42484 KiB
97Accepted20ms42348 KiB
98Accepted20ms42352 KiB
99Accepted20ms42480 KiB
100Wrong answer20ms42620 KiB
101Wrong answer20ms42496 KiB
102Accepted20ms42516 KiB
103Wrong answer20ms42508 KiB
104Wrong answer20ms42508 KiB
105Wrong answer20ms42744 KiB
106Accepted20ms42732 KiB
107Wrong answer20ms42776 KiB
108Wrong answer18ms42876 KiB
109Wrong answer17ms42896 KiB
110Wrong answer20ms42880 KiB
111Accepted90ms62808 KiB
112Accepted86ms63856 KiB
113Accepted86ms63820 KiB
114Accepted90ms64368 KiB
115Wrong answer97ms64268 KiB
116Wrong answer98ms64356 KiB
117Wrong answer101ms63356 KiB
118Wrong answer93ms63940 KiB
119Wrong answer103ms64468 KiB
120Wrong answer101ms64008 KiB
121Wrong answer92ms64488 KiB