#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
priority_queue<pair<pair<int,int>,int>,vector<pair<pair<int,int>,int>>,greater<pair<pair<int,int>,int>>> pq;
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.begin()) {
it--;
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.begin()) {
it--;
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;
int ps0[maxn], ps1[maxn];
for(int i = 0; i <= n; i++) {
ps0[i] = ps1[0] = 0;
}
for(auto x : segs) {
// cout << x.fr.fr << " " << x.fr.sc << " " << x.sc << endl;
}
for(int i = 0; i < m; i++) {
// cout << i << " -> " << vec[pai[i]].fr << " " << vec[pai[i]].sc << endl;
int a = vec[i].fr;
int b = vec[i].sc;
if(b >= a) {
if(ans[i] == 0) {
ps0[a]++;
ps0[b+1]--;
}
else {
ps1[a]++;
ps1[b+1]--;
}
}
else {
if(ans[i] == 0) {
ps0[b]++;
ps0[1]++;
ps0[a+1]--;
}
else {
ps1[b]++;
ps1[1]++;
ps1[a+1]--;
}
}
}
bool okk = false;
for(int i = 1; i <= n; i++) {
ps0[i]+= ps0[i-1];
ps1[i]+= ps1[i-1];
if(ps0[i] == 0 || ps1[i] == 0) {
okk = true;
}
}
if(okk) {
cout << n<<"--"<<m<<"---";
cout << segs[0].fr.fr<<"--"<<segs[0].fr.sc;
return;
}
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;
}
int ps0[maxn], ps1[maxn];
for(int i = 0; i <= n; i++) {
ps0[i] = ps1[0] = 0;
}
for(auto x : segs) {
// cout << x.fr.fr << " " << x.fr.sc << " " << x.sc << endl;
}
for(int i = 0; i < m; i++) {
// cout << i << " -> " << vec[pai[i]].fr << " " << vec[pai[i]].sc << endl;
int a = vec[i].fr;
int b = vec[i].sc;
if(b >= a) {
if(ans[i] == 0) {
ps0[a]++;
ps0[b+1]--;
}
else {
ps1[a]++;
ps1[b+1]--;
}
}
else {
if(ans[i] == 0) {
ps0[b]++;
ps0[1]++;
ps0[a+1]--;
}
else {
ps1[b]++;
ps1[1]++;
ps1[a+1]--;
}
}
}
bool okk = false;
for(int i = 1; i <= n; i++) {
ps0[i]+= ps0[i-1];
ps1[i]+= ps1[i-1];
if(ps0[i] == 0 || ps1[i] == 0) {
okk = true;
}
}
if(okk) {
// cout << "penis";
}
}
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:66:13: warning: unused variable 'l' [-Wunused-variable]
66 | int l = X.fr.fr;
| ^
alternating.cpp:140: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]
140 | for(int i = 0; i < segs.size(); i++) {
| ~~^~~~~~~~~~~~~
alternating.cpp:161:22: warning: variable 'x' set but not used [-Wunused-but-set-variable]
161 | for(auto x : segs) {
| ^
alternating.cpp:213: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]
213 | for(int i = 0; i+1 < segs.size(); i++) {
| ~~~~^~~~~~~~~~~~~
alternating.cpp:231: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]
231 | for(int j = i+1; j < segs.size(); j++) {
| ~~^~~~~~~~~~~~~
alternating.cpp:214:17: warning: unused variable 'l1' [-Wunused-variable]
214 | int l1 = segs[i].fr.fr;
| ^~
alternating.cpp:217:17: warning: unused variable 'r2' [-Wunused-variable]
217 | int r2 = segs[i+1].fr.sc;
| ^~
alternating.cpp:263: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]
263 | for(int j = 0; j < segs.size(); j++) {
| ~~^~~~~~~~~~~~~
alternating.cpp:248:17: warning: unused variable 'l1' [-Wunused-variable]
248 | int l1 = segs.back().fr.fr;
| ^~
alternating.cpp:251:17: warning: unused variable 'r2' [-Wunused-variable]
251 | int r2 = segs[0].fr.sc+n;
| ^~
alternating.cpp:295:14: warning: variable 'x' set but not used [-Wunused-but-set-variable]
295 | for(auto x : segs) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3412 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 |
3 ms |
3412 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 |
3 ms |
3412 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 |
63 ms |
13108 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 |
3 ms |
3412 KB |
no wires in direction 0 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
