109612024-04-21 14:03:17k_balintÉvzárócpp17Wrong answer 5/100136ms52500 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=2e5+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
1Accepted6ms11336 KiB
2Wrong answer93ms34204 KiB
subtask25/5
3Accepted111ms51388 KiB
4Accepted122ms51616 KiB
subtask30/7
5Accepted111ms51388 KiB
6Accepted122ms51616 KiB
7Runtime error122ms52080 KiB
8Runtime error115ms52500 KiB
9Runtime error128ms47168 KiB
10Runtime error136ms33876 KiB
subtask40/20
11Accepted136ms31796 KiB
12Accepted130ms30048 KiB
13Accepted133ms29788 KiB
14Accepted134ms30148 KiB
15Accepted128ms30612 KiB
16Runtime error126ms34104 KiB
subtask50/13
17Accepted7ms13148 KiB
18Accepted6ms13172 KiB
19Accepted6ms13104 KiB
20Accepted6ms13236 KiB
21Accepted6ms13444 KiB
22Accepted6ms13660 KiB
23Accepted6ms13768 KiB
24Accepted6ms13876 KiB
25Accepted7ms13964 KiB
26Accepted7ms14088 KiB
27Accepted7ms14128 KiB
28Accepted7ms14208 KiB
29Accepted7ms14324 KiB
30Accepted7ms14204 KiB
31Wrong answer7ms14212 KiB
32Wrong answer7ms14208 KiB
33Wrong answer6ms14208 KiB
subtask60/20
34Accepted7ms13148 KiB
35Accepted6ms13172 KiB
36Accepted6ms13104 KiB
37Accepted6ms13236 KiB
38Accepted6ms13444 KiB
39Accepted6ms13660 KiB
40Accepted6ms13768 KiB
41Accepted6ms13876 KiB
42Accepted7ms13964 KiB
43Accepted7ms14088 KiB
44Accepted7ms14128 KiB
45Accepted7ms14208 KiB
46Accepted7ms14324 KiB
47Accepted7ms14204 KiB
48Wrong answer7ms14212 KiB
49Wrong answer7ms14208 KiB
50Wrong answer6ms14208 KiB
51Accepted7ms14292 KiB
52Accepted7ms14316 KiB
53Accepted7ms14472 KiB
54Accepted7ms14300 KiB
55Wrong answer7ms14452 KiB
56Wrong answer6ms14436 KiB
57Accepted8ms14432 KiB
58Wrong answer7ms14320 KiB
59Wrong answer7ms14584 KiB
60Wrong answer7ms14680 KiB
61Accepted7ms14684 KiB
62Wrong answer7ms14696 KiB
63Wrong answer7ms14660 KiB
64Wrong answer8ms14828 KiB
65Wrong answer8ms14812 KiB
subtask70/35
66Accepted7ms13148 KiB
67Wrong answer97ms37172 KiB
68Accepted111ms51388 KiB
69Accepted122ms51616 KiB
70Runtime error122ms52080 KiB
71Runtime error115ms52500 KiB
72Runtime error128ms47168 KiB
73Runtime error136ms33876 KiB
74Accepted136ms31796 KiB
75Accepted130ms30048 KiB
76Accepted133ms29788 KiB
77Accepted134ms30148 KiB
78Accepted128ms30612 KiB
79Runtime error126ms34104 KiB
80Accepted6ms13172 KiB
81Accepted6ms13104 KiB
82Accepted6ms13236 KiB
83Accepted6ms13444 KiB
84Accepted6ms13660 KiB
85Accepted6ms13768 KiB
86Accepted6ms13876 KiB
87Accepted7ms13964 KiB
88Accepted7ms14088 KiB
89Accepted7ms14128 KiB
90Accepted7ms14208 KiB
91Accepted7ms14324 KiB
92Accepted7ms14204 KiB
93Wrong answer7ms14212 KiB
94Wrong answer7ms14208 KiB
95Wrong answer6ms14208 KiB
96Accepted7ms14292 KiB
97Accepted7ms14316 KiB
98Accepted7ms14472 KiB
99Accepted7ms14300 KiB
100Wrong answer7ms14452 KiB
101Wrong answer6ms14436 KiB
102Accepted8ms14432 KiB
103Wrong answer7ms14320 KiB
104Wrong answer7ms14584 KiB
105Wrong answer7ms14680 KiB
106Accepted7ms14684 KiB
107Wrong answer7ms14696 KiB
108Wrong answer7ms14660 KiB
109Wrong answer8ms14828 KiB
110Wrong answer8ms14812 KiB
111Accepted82ms34616 KiB
112Accepted79ms35624 KiB
113Accepted76ms35628 KiB
114Accepted82ms36144 KiB
115Wrong answer82ms36012 KiB
116Wrong answer85ms36120 KiB
117Wrong answer87ms35308 KiB
118Wrong answer83ms35712 KiB
119Wrong answer87ms36212 KiB
120Wrong answer90ms35700 KiB
121Wrong answer83ms36216 KiB