157442025-02-25 18:33:51TaxiradioÉvzárócpp17Wrong answer 12/100345ms30756 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

#define int int64_t

const int k = 2000000000;

vector<array<int , 3>> e;
vector<vector<array<int , 2>>> g;
vector<int> ans;
vector<int> a;
int u = 0;
int l = 0;
int n; 

void dfs(int h){
    while(!g[h].empty()){
        if(ans[g[h].back()[1]] != -1){
            g[h].pop_back();
            continue;
        }
        int s = g[h].back()[1], d  = g[h].back()[0];
        ans[s] = 2;
        dfs(g[h].back()[0]);
        ans[s] = l;
        if(s < n)l = !l;
    }
}

int32_t main() {
    cin >> n;
    ans.resize(n*2+3 , -1);
    g.resize(n*2+3);
    for(int i = 0; i < n;i++){
        int y , z; cin >> y >> z;
        a.push_back(y);
        a.push_back(z+k);
        e.push_back({y , z+k , u++});
    }
    sort(a.begin() , a.end());
    a.erase(unique(a.begin(),a.end()),a.end());
    for(int i = 0; i < n;i++){
        e[i][0] = lower_bound(a.begin() , a.end() , e[i][0])-a.begin();
        e[i][1] = lower_bound(a.begin() , a.end() , e[i][1])-a.begin();
        g[e[i][0]].push_back({e[i][1] , e[i][2]});
        g[e[i][1]].push_back({e[i][0] , e[i][2]});
    }
    int r = -1;
    for(int i = 0; i < g.size();i++){
        if(g[i].size()%2 == 1){
            if(r == -1){
                r = i;
                continue;
            }
            g[i].push_back({r , u});
            g[r].push_back({i , u++});
            r = -1; 
        }
    }
    for(int i = 0; i < g.size();i++)if(g[i].size() != 0)dfs(i);
    for(int i = 0; i < n;i++){
        if(ans[i]){
            cout << "L";
        }else{
            cout << "F";
        }
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted171ms20496 KiB
subtask25/5
3Accepted200ms24868 KiB
4Accepted203ms24868 KiB
subtask37/7
5Accepted200ms24868 KiB
6Accepted203ms24868 KiB
7Accepted214ms25196 KiB
8Accepted245ms25476 KiB
9Accepted268ms25776 KiB
10Accepted345ms30756 KiB
subtask40/20
11Accepted240ms18728 KiB
12Wrong answer223ms18144 KiB
13Wrong answer224ms18144 KiB
14Wrong answer238ms18176 KiB
15Accepted219ms18320 KiB
16Accepted303ms27396 KiB
subtask50/13
17Accepted1ms316 KiB
18Accepted1ms316 KiB
19Accepted1ms316 KiB
20Accepted1ms316 KiB
21Accepted1ms316 KiB
22Accepted1ms316 KiB
23Accepted1ms316 KiB
24Wrong answer1ms316 KiB
25Accepted1ms316 KiB
26Accepted1ms316 KiB
27Accepted1ms316 KiB
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Accepted1ms404 KiB
subtask60/20
34Accepted1ms316 KiB
35Accepted1ms316 KiB
36Accepted1ms316 KiB
37Accepted1ms316 KiB
38Accepted1ms316 KiB
39Accepted1ms316 KiB
40Accepted1ms316 KiB
41Wrong answer1ms316 KiB
42Accepted1ms316 KiB
43Accepted1ms316 KiB
44Accepted1ms316 KiB
45Accepted1ms316 KiB
46Accepted1ms316 KiB
47Accepted1ms316 KiB
48Accepted1ms316 KiB
49Accepted1ms316 KiB
50Accepted1ms404 KiB
51Wrong answer3ms580 KiB
52Wrong answer2ms564 KiB
53Wrong answer3ms756 KiB
54Accepted3ms564 KiB
55Accepted2ms564 KiB
56Accepted2ms564 KiB
57Accepted2ms564 KiB
58Accepted2ms564 KiB
59Accepted2ms564 KiB
60Accepted2ms620 KiB
61Accepted2ms564 KiB
62Accepted2ms564 KiB
63Accepted2ms564 KiB
64Accepted2ms564 KiB
65Accepted2ms564 KiB
subtask70/35
66Accepted1ms316 KiB
67Accepted179ms20432 KiB
68Accepted200ms24868 KiB
69Accepted203ms24868 KiB
70Accepted214ms25196 KiB
71Accepted245ms25476 KiB
72Accepted268ms25776 KiB
73Accepted345ms30756 KiB
74Accepted240ms18728 KiB
75Wrong answer223ms18144 KiB
76Wrong answer224ms18144 KiB
77Wrong answer238ms18176 KiB
78Accepted219ms18320 KiB
79Accepted303ms27396 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted1ms316 KiB
84Accepted1ms316 KiB
85Accepted1ms316 KiB
86Wrong answer1ms316 KiB
87Accepted1ms316 KiB
88Accepted1ms316 KiB
89Accepted1ms316 KiB
90Accepted1ms316 KiB
91Accepted1ms316 KiB
92Accepted1ms316 KiB
93Accepted1ms316 KiB
94Accepted1ms316 KiB
95Accepted1ms404 KiB
96Wrong answer3ms580 KiB
97Wrong answer2ms564 KiB
98Wrong answer3ms756 KiB
99Accepted3ms564 KiB
100Accepted2ms564 KiB
101Accepted2ms564 KiB
102Accepted2ms564 KiB
103Accepted2ms564 KiB
104Accepted2ms564 KiB
105Accepted2ms620 KiB
106Accepted2ms564 KiB
107Accepted2ms564 KiB
108Accepted2ms564 KiB
109Accepted2ms564 KiB
110Accepted2ms564 KiB
111Accepted158ms19272 KiB
112Accepted152ms20256 KiB
113Accepted148ms20176 KiB
114Accepted153ms20268 KiB
115Accepted159ms20516 KiB
116Accepted164ms20528 KiB
117Accepted159ms19752 KiB
118Accepted156ms20260 KiB
119Accepted158ms20760 KiB
120Accepted166ms19752 KiB
121Accepted158ms20520 KiB