#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 2e5+10;
int n, m, pai[maxn], ps[maxn], ans[maxn], bit[maxn];
void att(int pos) {
for(int i = pos; i <= 2*n; i+= i&-i) bit[i]++;
}
int qrr(int pos) {
int val = 0;
for(int i = pos; i > 0; i-=i&-i) val+= bit[i];
return val;
}
bool cmp(pair<pair<int,int>,int> a, pair<pair<int,int>,int> b) {
if(a.fr.fr == b.fr.fr) {
return a.fr.sc > b.fr.sc;
}
return a.fr.fr < b.fr.fr;
}
void solve() {
cin >> n >> m;
vector<pair<pair<int,int>,int>> segs;
vector<pair<int,int>> vec;
for(int i = 0; i < m; i++) {
int a,b; cin >> a >> b;
vec.pb(mp(a,b));
pai[i] = i;
if(b >= a) {
ps[a]++;
ps[b+1]--;
ps[a+n]++;
ps[b+n+1]--;
segs.pb(mp(mp(a,b),i));
segs.pb(mp(mp(a+n,b+n),i));
}
else {
ps[a]++;
ps[b+n+1]--;
ps[1]++;
ps[b+1]--;
ps[a+n]++;
ps[2*n+1]--;
segs.pb(mp(mp(a,b+n),i));
}
}
sort(all(segs),cmp); //menor L, maior R
for(auto X : segs) {
int l = X.fr.fr;
int r = X.fr.sc;
int id = X.sc;
if(qrr(2*n-r+1) > 0) {
pai[id] = -1;
}
att(2*n-r+1);
}
segs.clear();
for(int i = 0; i < m; i++) {
// cout << i << " " << pai[i] << endl;
if(pai[i] == i) {
int a = vec[i].fr;
int b = vec[i].sc;
if(b >= a) {
segs.pb(mp(mp(a,b),i));
}
else {
segs.pb(mp(mp(a,b+n),i));
}
}
}
sort(all(segs));
for(int i = 0; i < m; i++) {
if(pai[i] == i) continue;
int l1 = vec[i].fr;
int r1 = vec[i].sc;
//ve o ultimo com l menor ou igual a l1
auto it = lower_bound(all(segs),mp(mp(l1,inf),0LL));
if(it != segs.end()) {
int l2,r2,id;
l2 = it->fr.fr;
r2 = it->fr.sc;
id = it->sc;
//ve se da certo com esse
if(l1 >= l2 && r1 <= r2) {
pai[i] = id;
continue;
}
}
//tenta com l1+n e r1+n
l1+= n;
r1+= n;
it = lower_bound(all(segs),mp(mp(l1,inf),0LL));
if(it != segs.end()) {
int l2,r2,id;
l2 = it->fr.fr;
r2 = it->fr.sc;
id = it->sc;
//ve se da certo com esse
if(l1 >= l2 && r1 <= r2) {
pai[i] = id;
continue;
}
}
}
bool ok = true;
for(int i = 1; i <= 2*n; i++) {
ps[i]+=ps[i-1];
if(ps[i] < 2) ok = false;
}
if(!ok) {
cout << "impossible" << endl;
return;
}
if((((int) segs.size())&1) == 0) {
for(int i = 0; i < segs.size(); i++) {
int id = segs[i].sc;
ans[id] = i&1;
}
for(int i = 0; i < m; i++) {
if(pai[i] == i) continue;
ans[i] = ans[pai[i]]^1;
}
for(int i = 0; i < m; i++) {
cout << ans[i];
}cout << endl;
}
else {
if(segs.size() == 1) {
ans[segs[0].sc] = 1;
for(int i = 0; i < m; i++) {
cout << ans[i];
}cout << endl;
return;
}
bool ok = false;
for(int i = 0; i+1 < segs.size(); i++) {
int l1 = segs[i].fr.fr;
int r1 = segs[i].fr.sc;
int l2 = segs[i+1].fr.fr;
int r2 = segs[i+1].fr.sc;
//a area coberta por dois é l2 até r1
int l = l2;
int r = r1;
bool ok1 = true;
for(int i = l; i <= r; i++) {
if(ps[i] < 3) {
ok1 = false;
break;
}
}
if(ok1) {
int cnt = 0;
for(int j = i+1; j < segs.size(); j++) {
int id = segs[j].sc;
ans[id]=cnt;
cnt^=1;
}
for(int j = 0; j <= i; j++) {
int id = segs[j].sc;
ans[id]=cnt;
cnt^=1;
}
ok = true;
break;
}
}
if(ok == false) {
//ultimo com o primeiro
int l1 = segs.back().fr.fr;
int r1 = segs.back().fr.sc;
int l2 = segs[0].fr.fr+n;
int r2 = segs[0].fr.sc+n;
int l = l2;
int r = r1;
bool ok1 = true;
for(int i = l; i <= r; i++) {
if(ps[i] < 3) {
ok1 = false;
break;
}
}
if(ok1) {
int cnt = 0;
for(int j = 0; j < segs.size(); j++) {
int id = segs[j].sc;
ans[id]=cnt;
cnt^=1;
}
ok = true;
}
}
if(ok == false) {
cout << "impossible" << endl;
return;
}
for(int i = 0; i < m; i++) {
if(pai[i] == i) continue;
ans[i] = ans[pai[i]]^1;
}
for(int i = 0; i < m; i++) {
cout << ans[i];
}cout << endl;
}
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
}
Compilation message
alternating.cpp: In function 'void solve()':
alternating.cpp:65:13: warning: unused variable 'l' [-Wunused-variable]
65 | int l = X.fr.fr;
| ^
alternating.cpp:137:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int i = 0; i < segs.size(); i++) {
| ~~^~~~~~~~~~~~~
alternating.cpp:159:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | for(int i = 0; i+1 < segs.size(); i++) {
| ~~~~^~~~~~~~~~~~~
alternating.cpp:177:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | for(int j = i+1; j < segs.size(); j++) {
| ~~^~~~~~~~~~~~~
alternating.cpp:160:17: warning: unused variable 'l1' [-Wunused-variable]
160 | int l1 = segs[i].fr.fr;
| ^~
alternating.cpp:163:17: warning: unused variable 'r2' [-Wunused-variable]
163 | int r2 = segs[i+1].fr.sc;
| ^~
alternating.cpp:209:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
209 | for(int j = 0; j < segs.size(); j++) {
| ~~^~~~~~~~~~~~~
alternating.cpp:194:17: warning: unused variable 'l1' [-Wunused-variable]
194 | int l1 = segs.back().fr.fr;
| ^~
alternating.cpp:197:17: warning: unused variable 'r2' [-Wunused-variable]
197 | int r2 = segs[0].fr.sc+n;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
no wires in direction 0 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
no wires in direction 0 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
no wires in direction 0 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
10052 KB |
no wires in direction 0 between segments 1 and 100000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
no wires in direction 0 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
