提出 #61638866

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())

#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl '\n' // remove in interactive
#endif

void solve(){
	int n, m;
	cin >> n >> m;
	vector<int> l(m), r(m), perm(m);
	int one = -1;
	int ml = -1, MR = -1;
	for(int i = 0; i < m; i++){
		cin >> l[i] >> r[i];
		perm[i] = i;
		if(l[i]==1 && r[i] == n) one = i;
		if(l[i] == 1){
			if(MR == -1 || r[MR] < r[i]) MR = i;
		}
		if(r[i] == n){
			if(ml == -1 || l[ml] > l[i]) ml = i;
		}
	}
	if(one != -1){
		cout << 1 << endl;
		for(int i = 0; i < m; i++) cout << (i == one ? 1 : 0) << " ";
		cout << endl;
		return;
	}
	sort(all(perm), [&](int i, int j){return l[i] < l[j] || (l[i] == l[j] && r[i] > r[j]);});
	int max_l = perm[0], min_r = perm[0];
	
	for(int i = 1; i < m; i++){
		int x = perm[i], y = perm[i - 1];
		if(l[x] > l[max_l]) max_l = x;
		if(r[x] < r[min_r]) min_r = x;
		if(r[x] <= r[y]){
			cout << 2 << endl;
			for(int j = 0; j < m; j++){
				int v = 0;
				if(j == x) v = 2;
				if(j == y) v = 1;
				cout << v << " ";
			}
			cout << endl;
			return;
		}
	}

	if(l[max_l] > r[min_r]){
		cout << 2 << endl;
		for(int i = 0; i < m;i++){
			cout << ((i == max_l || i == min_r) ?  2 : 0) << " ";
		}
		cout << endl;
		return;
	}
	if(ml != -1 && MR != -1 && l[ml] <= r[MR]){
		cout << 2 << endl;
		for(int i = 0; i < m; i++){
			cout << ((i == ml || i == MR) ? 1 : 0) << " ";
		}
		cout << endl;
		return;
	}
	if(m <= 2){
		cout << -1 << endl;
		return;
	}
	cout << 3 << endl;
	int done = 0;
	for(int i = 0; i < m; i++){
		int v = 0;
		if(i == max_l || i == min_r) v = 2;
		if(!done && !v) v = done = 1;
		cout << v << " ";
	}
	cout << endl;
}

int main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); // Remove in interactive problems
	int t = 1;
	// cin >> t;
	while(t--){
		solve();
	}
}

提出情報

ジャッジ結果