#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
const int inf = 1e9;
int main(){
int n , m;
cin >> n >> m;
vector < pair < int , int > > lines(m);
for(int i = 0 ; i < m; ++i){
int l , r;
cin >> l >> r;
lines[i] = {l , r};
}
vector < bool > used(m);
vector < int > answer(m);
/// try to do it
auto get_len = [&n](pair < int , int > line){
int cur_len = (line.se + n - line.fi) + 1;
if(cur_len > n)
cur_len -= n;
return cur_len;
};
auto move_seg = [&n](int &seg){
seg++;
if(seg == n + 1)
seg = 1;
};
auto come_through = [&lines, &n](int id , int seg){
if(lines[id].first <= lines[id].second){
if(seg >= lines[id].first && seg <= lines[id].second)
return true;
else
return false;
}
if(seg >= lines[id].first && seg <= n)
return true;
if(seg >= 1 && seg <= lines[id].second)
return true;
return false;
};
// cerr << " LENS \n";
// for(int i = 0 ; i < m; ++i)
// cerr << get_len(lines[i]) << ' ';
// cerr << '\n';
auto tryy = [&](int type){
int best_len = -1 , best_line = -1;
for(int i = 0; i < m; ++i){
if(used[i])
continue;
int cur_len = get_len(lines[i]);
if(best_len < cur_len){
best_len = cur_len;
best_line = i;
}
}
if(best_line == -1)
return false;
int done = 0;
done += get_len(lines[best_line]);
vector < bool > segments_done(n + 1);
used[best_line] = 1;
answer[best_line] = type;
int seg = lines[best_line].first;
for(int it = 0; it < done; ++it){
segments_done[seg] = 1;
move_seg(seg);
}
while(done < n){
while(segments_done[seg]){
move_seg(seg);
}
// cerr << " done " << done << '\n';
int cur_best_line = -1 , cur_best_val = inf;
for(int x = 0 ; x < m; ++x){
if(used[x])
continue;
if(come_through(x , seg)){
int val = 0;
int po_seg = lines[x].fi;
for(int it = 0 ; it < get_len(lines[x]); ++it){
if(segments_done[po_seg])
val++;
move_seg(po_seg);
}
if(val < cur_best_val){
cur_best_val = val;
cur_best_line = x;
}
}
}
/// use it
//// cerr << done << '\n';
if(cur_best_line == -1)
return false;
int po_seg = lines[cur_best_line].fi;
for(int it = 0 ; it < get_len(lines[cur_best_line]); ++it){
if(!segments_done[po_seg])
done++ , segments_done[po_seg] = 1;
move_seg(po_seg);
}
used[cur_best_line] = 1;
answer[cur_best_line] = type;
}
// for(int i = 0 ; i < m; ++i)
// cerr << used[i] << ' ';
// cerr << '\n';
// cerr << done << endl;
return true;
};
// cerr << tryy(0) << endl;
// cerr << tryy(1) << endl;
if(!tryy(0) || !tryy(1))
cout << "impossible\n";
else{
for(int i = 0 ; i < m; ++i)
cout << answer[i];
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
296 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
296 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
296 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
296 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
296 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
296 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
2464 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
31 ms |
1448 KB |
Output is correct |
| 4 |
Correct |
34 ms |
1444 KB |
Output is correct |
| 5 |
Execution timed out |
3086 ms |
2424 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
296 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
296 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
