#include <bits/stdc++.h>
#define int long long
using namespace std;
int INF = 1LL<<30;
int n,m;
vector<pair<int,int>> segments;
vector<int> indices,invindices;
bool inside(int a, int b, int c) {
//is it a,b,c in this order?
bool ans = (a<=b && b<=c) || (a<=b && b>c && c<a) || (a>b && b<=c && c<a);
////cout << a <<" " << b <<" " << c <<" " << ans << endl;
return ans;
}
bool between(pair<int,int> s1, pair<int,int> s2) {
//is s2 fully between s1's endpoints
int a=s1.first; int b = s1.second; int c = s2.first; int d = s2.second;
bool ans = inside(a,c,d) && inside(c,d,b) && inside(a,c,b) && inside(a,d,b);
////cout << a <<" " << b <<" " << c <<" " <<d << " " << ans << endl;
return ans;
}
bool works(vector<int> ans) {
//1 implies 0-covered, 2 implies 1-covered
set<int> remset0;
set<int> remset1;
for (int i=0; i<n; i++) {
remset0.insert(i); remset1.insert(i);
}
for (int i1=0; i1<m; i1++) {
int l = segments[i1].first;
int r = segments[i1].second;
for (int i=l; i!=r; ) {
//cout << "erasing " << i <<" " << l <<" " <<r <<" " << ans[i1] << endl;
if (ans[i1]==0 && remset0.count(i)) {
remset0.erase(i);
}
if (ans[i1]==1 && remset1.count(i)) {
remset1.erase(i);
}
i++; i%=n;
}
if (ans[i1]==0 && remset0.count(r)) {
remset0.erase(r);
}
if (ans[i1]==1 && remset1.count(r)) {
remset1.erase(r);
}
}
return (remset0.size()==0) && (remset1.size()==0);
}
void print_ans(vector<int> answer){
for (int i=0; i<m; i++) {
//cout << invindices[i] <<" ";
}
//cout << endl;
for (int i=0; i<m; i++) {
cout << answer[invindices[i]];
}
cout << endl;
}
signed main() {
#ifndef ONLINE_JUDGE
// for getting input from input.txt
//freopen("input.txt", "r", stdin);
// for writing output to output.txt
//freopen("output.txt", "w", stdout);
#endif
#ifdef ONLINE_JUDGE
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#endif //fast IO
cin >> n >> m;
vector<int> answer(m,-1);
indices=invindices=vector<int>(m); iota(indices.begin(), indices.end(), (int)0);
for (int i=0; i<m; i++) {
int s,t; cin >> s >> t; s--; t--;
segments.push_back({s,t}); //subtask 4: t>s
}
stable_sort(indices.begin(), indices.end(), [&](const int i1, const int i2) {
return segments[i1]<segments[i2];
});
for (int i=0; i<m; i++) {
invindices[indices[i]] = i;
}
stable_sort(segments.begin(), segments.end());
vector<int> goods;
vector<int> covered_by(m,-1);
for (int i=0; i<m; i++) {
for (int j=0; j<m; j++) {
if (j==i) continue;
//if i is covered by j
if (between(segments[j],segments[i])) {
covered_by[i] = j;
}
}
if (covered_by[i]==-1) {
goods.push_back(i);
}
}
for (int i=0; i<m; i++) {
//cout << i << " " << covered_by[i] << endl;
}
int k = goods.size();
if (goods.size()%2==0) {
for (int i=0; i<k; i++) {
//cout << "setting " << goods[i] <<" " << i%2 << endl;
answer[goods[i]] = i%2;
}
for (int i=0; i<m; i++) {
if (covered_by[i]!=-1) {
//cout << "setting2 " << i <<" " << covered_by[i] <<" " <<answer[covered_by[i]] << endl;
answer[i] = 1-answer[covered_by[i]];
}
}
for (int i=0; i<m; i++) {
if (answer[i]!=0 && answer[i]!=1) {
answer[i] = 0;
}
}
}
else {
for (int tau=0; tau<m; tau++) {
for (int i=0; i<tau; i++) {
answer[goods[i]] = i%2;
}
for (int i=tau+1; i<k; i++) {
answer[goods[i]] = (i+1)%2;
}
for (int i=0; i<m; i++) {
if (covered_by[i]!=-1) {
answer[i] = 1-answer[covered_by[i]];
}
}
for (int i=0; i<m; i++) {
if (answer[i]!=0 && answer[i]!=1) {
answer[i] = 0;
}
}
if (works(answer)) {
break;
}
}
}
//cout << "trying answer " << endl;
if (works(answer)) {
print_ans(answer);
}
else {
cout << "impossible" << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
'impossible' claimed, but there is a solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
'impossible' claimed, but there is a solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
'impossible' claimed, but there is a solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3047 ms |
6240 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
'impossible' claimed, but there is a solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
