// 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";
}
}
}
| Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 1ms | 316 KiB | ||||
| 2 | Elfogadva | 171ms | 20496 KiB | ||||
| subtask2 | 5/5 | ||||||
| 3 | Elfogadva | 200ms | 24868 KiB | ||||
| 4 | Elfogadva | 203ms | 24868 KiB | ||||
| subtask3 | 7/7 | ||||||
| 5 | Elfogadva | 200ms | 24868 KiB | ||||
| 6 | Elfogadva | 203ms | 24868 KiB | ||||
| 7 | Elfogadva | 214ms | 25196 KiB | ||||
| 8 | Elfogadva | 245ms | 25476 KiB | ||||
| 9 | Elfogadva | 268ms | 25776 KiB | ||||
| 10 | Elfogadva | 345ms | 30756 KiB | ||||
| subtask4 | 0/20 | ||||||
| 11 | Elfogadva | 240ms | 18728 KiB | ||||
| 12 | Hibás válasz | 223ms | 18144 KiB | ||||
| 13 | Hibás válasz | 224ms | 18144 KiB | ||||
| 14 | Hibás válasz | 238ms | 18176 KiB | ||||
| 15 | Elfogadva | 219ms | 18320 KiB | ||||
| 16 | Elfogadva | 303ms | 27396 KiB | ||||
| subtask5 | 0/13 | ||||||
| 17 | Elfogadva | 1ms | 316 KiB | ||||
| 18 | Elfogadva | 1ms | 316 KiB | ||||
| 19 | Elfogadva | 1ms | 316 KiB | ||||
| 20 | Elfogadva | 1ms | 316 KiB | ||||
| 21 | Elfogadva | 1ms | 316 KiB | ||||
| 22 | Elfogadva | 1ms | 316 KiB | ||||
| 23 | Elfogadva | 1ms | 316 KiB | ||||
| 24 | Hibás válasz | 1ms | 316 KiB | ||||
| 25 | Elfogadva | 1ms | 316 KiB | ||||
| 26 | Elfogadva | 1ms | 316 KiB | ||||
| 27 | Elfogadva | 1ms | 316 KiB | ||||
| 28 | Elfogadva | 1ms | 316 KiB | ||||
| 29 | Elfogadva | 1ms | 316 KiB | ||||
| 30 | Elfogadva | 1ms | 316 KiB | ||||
| 31 | Elfogadva | 1ms | 316 KiB | ||||
| 32 | Elfogadva | 1ms | 316 KiB | ||||
| 33 | Elfogadva | 1ms | 404 KiB | ||||
| subtask6 | 0/20 | ||||||
| 34 | Elfogadva | 1ms | 316 KiB | ||||
| 35 | Elfogadva | 1ms | 316 KiB | ||||
| 36 | Elfogadva | 1ms | 316 KiB | ||||
| 37 | Elfogadva | 1ms | 316 KiB | ||||
| 38 | Elfogadva | 1ms | 316 KiB | ||||
| 39 | Elfogadva | 1ms | 316 KiB | ||||
| 40 | Elfogadva | 1ms | 316 KiB | ||||
| 41 | Hibás válasz | 1ms | 316 KiB | ||||
| 42 | Elfogadva | 1ms | 316 KiB | ||||
| 43 | Elfogadva | 1ms | 316 KiB | ||||
| 44 | Elfogadva | 1ms | 316 KiB | ||||
| 45 | Elfogadva | 1ms | 316 KiB | ||||
| 46 | Elfogadva | 1ms | 316 KiB | ||||
| 47 | Elfogadva | 1ms | 316 KiB | ||||
| 48 | Elfogadva | 1ms | 316 KiB | ||||
| 49 | Elfogadva | 1ms | 316 KiB | ||||
| 50 | Elfogadva | 1ms | 404 KiB | ||||
| 51 | Hibás válasz | 3ms | 580 KiB | ||||
| 52 | Hibás válasz | 2ms | 564 KiB | ||||
| 53 | Hibás válasz | 3ms | 756 KiB | ||||
| 54 | Elfogadva | 3ms | 564 KiB | ||||
| 55 | Elfogadva | 2ms | 564 KiB | ||||
| 56 | Elfogadva | 2ms | 564 KiB | ||||
| 57 | Elfogadva | 2ms | 564 KiB | ||||
| 58 | Elfogadva | 2ms | 564 KiB | ||||
| 59 | Elfogadva | 2ms | 564 KiB | ||||
| 60 | Elfogadva | 2ms | 620 KiB | ||||
| 61 | Elfogadva | 2ms | 564 KiB | ||||
| 62 | Elfogadva | 2ms | 564 KiB | ||||
| 63 | Elfogadva | 2ms | 564 KiB | ||||
| 64 | Elfogadva | 2ms | 564 KiB | ||||
| 65 | Elfogadva | 2ms | 564 KiB | ||||
| subtask7 | 0/35 | ||||||
| 66 | Elfogadva | 1ms | 316 KiB | ||||
| 67 | Elfogadva | 179ms | 20432 KiB | ||||
| 68 | Elfogadva | 200ms | 24868 KiB | ||||
| 69 | Elfogadva | 203ms | 24868 KiB | ||||
| 70 | Elfogadva | 214ms | 25196 KiB | ||||
| 71 | Elfogadva | 245ms | 25476 KiB | ||||
| 72 | Elfogadva | 268ms | 25776 KiB | ||||
| 73 | Elfogadva | 345ms | 30756 KiB | ||||
| 74 | Elfogadva | 240ms | 18728 KiB | ||||
| 75 | Hibás válasz | 223ms | 18144 KiB | ||||
| 76 | Hibás válasz | 224ms | 18144 KiB | ||||
| 77 | Hibás válasz | 238ms | 18176 KiB | ||||
| 78 | Elfogadva | 219ms | 18320 KiB | ||||
| 79 | Elfogadva | 303ms | 27396 KiB | ||||
| 80 | Elfogadva | 1ms | 316 KiB | ||||
| 81 | Elfogadva | 1ms | 316 KiB | ||||
| 82 | Elfogadva | 1ms | 316 KiB | ||||
| 83 | Elfogadva | 1ms | 316 KiB | ||||
| 84 | Elfogadva | 1ms | 316 KiB | ||||
| 85 | Elfogadva | 1ms | 316 KiB | ||||
| 86 | Hibás válasz | 1ms | 316 KiB | ||||
| 87 | Elfogadva | 1ms | 316 KiB | ||||
| 88 | Elfogadva | 1ms | 316 KiB | ||||
| 89 | Elfogadva | 1ms | 316 KiB | ||||
| 90 | Elfogadva | 1ms | 316 KiB | ||||
| 91 | Elfogadva | 1ms | 316 KiB | ||||
| 92 | Elfogadva | 1ms | 316 KiB | ||||
| 93 | Elfogadva | 1ms | 316 KiB | ||||
| 94 | Elfogadva | 1ms | 316 KiB | ||||
| 95 | Elfogadva | 1ms | 404 KiB | ||||
| 96 | Hibás válasz | 3ms | 580 KiB | ||||
| 97 | Hibás válasz | 2ms | 564 KiB | ||||
| 98 | Hibás válasz | 3ms | 756 KiB | ||||
| 99 | Elfogadva | 3ms | 564 KiB | ||||
| 100 | Elfogadva | 2ms | 564 KiB | ||||
| 101 | Elfogadva | 2ms | 564 KiB | ||||
| 102 | Elfogadva | 2ms | 564 KiB | ||||
| 103 | Elfogadva | 2ms | 564 KiB | ||||
| 104 | Elfogadva | 2ms | 564 KiB | ||||
| 105 | Elfogadva | 2ms | 620 KiB | ||||
| 106 | Elfogadva | 2ms | 564 KiB | ||||
| 107 | Elfogadva | 2ms | 564 KiB | ||||
| 108 | Elfogadva | 2ms | 564 KiB | ||||
| 109 | Elfogadva | 2ms | 564 KiB | ||||
| 110 | Elfogadva | 2ms | 564 KiB | ||||
| 111 | Elfogadva | 158ms | 19272 KiB | ||||
| 112 | Elfogadva | 152ms | 20256 KiB | ||||
| 113 | Elfogadva | 148ms | 20176 KiB | ||||
| 114 | Elfogadva | 153ms | 20268 KiB | ||||
| 115 | Elfogadva | 159ms | 20516 KiB | ||||
| 116 | Elfogadva | 164ms | 20528 KiB | ||||
| 117 | Elfogadva | 159ms | 19752 KiB | ||||
| 118 | Elfogadva | 156ms | 20260 KiB | ||||
| 119 | Elfogadva | 158ms | 20760 KiB | ||||
| 120 | Elfogadva | 166ms | 19752 KiB | ||||
| 121 | Elfogadva | 158ms | 20520 KiB | ||||