This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <iostream>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
#include <random>
#include <chrono>
using namespace std;
#define ll long long
#define ld long double
const int MX = 5005;
const int BLOCK = 105;
const ll inf = 8000000000000000069ll;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
const int dxh[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dyh[] = {2, -2, 2, -2, 1, -1, 1, -1}; // horse
const int dx[] = {1, -1, 0, 0, 0, 0};
const int dy[] = {0, 0, 1, -1, 0, 0}; // adj
const int dz[] = {0, 0, 0, 0, 1, -1};
const int dxd[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int dyd[] = {1, 0, -1, -1, -1, 0, 1, 1}; // diag
mt19937 rng(time(NULL));
int n, m;
vector<pair<pair<int, int>, int> > v;
void imp(){
cout << "impossible\n";
exit(0);
}
void solve(){
set<pair<int, int> > s;
vector<int> ans(m + 1, 0);
int c1 = 0, c2 = 0;
for(int j = 0, i = 1; i <= n; i ++){
for(; j < m && v[j].first.first == i; j ++)
s.insert(make_pair(v[j].first.second, v[j].second));
for(; s.size() && s.begin() -> first < i;)
s.erase(s.begin());
if(c1 < i){
if(s.empty()) imp();
c1 = s.begin() -> first;
ans[s.begin() -> second] = 1;
s.erase(s.begin());
}
if(c2 < i){
if(s.empty()) imp();
c2 = s.begin() -> first;
ans[s.begin() -> second] = 0;
s.erase(s.begin());
}
}
for(int i = 0; i < m; i ++)
cout << ans[i];
exit(0);
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> m;
v.resize(m);
bool aa = 1;
for(int i = 0; i < m; i ++){
cin >> v[i].first.first >> v[i].first.second;
if(v[i].first.first > v[i].first.second) aa = 0;
v[i].second = i;
}
sort(v.begin(), v.end());
if(aa) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |