Submission #61638323

---

Source Code Expand

#ifdef ONPC
#define _GLIBCXX_DEBUG
#else
#pragma GCC optimize("O3")
#endif

// #include <bits/stdc++.h>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <math.h>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <stdio.h>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cassert>
#include <tuple>
#include <iostream>
#include <set>
#include <stdexcept>

#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define int ll

using namespace std;

typedef int64_t ll;
// typedef __int128_t lll;
typedef uint64_t ull;
typedef long double ld;

template <typename T>
void PrintV(vector<T> v)
{
    for (T x : v)
    {
        cout << x << " ";
    }
    cout << "\n";
}

ll GCD(ll a, ll b)
{
    if (b == 0)
    {
        return abs(a);
    }
    return GCD(b, a % b);
}

const ll mod = 998244353; // 1e9 + 7; // 998244353;

ll sum(ll a, ll b)
{
    return (a + b) % mod;
}

ll mult(ll a, ll b)
{
    return (a * b) % mod;
}

ll binpow(ll x, ll pw)
{
    if (pw == 0)
    {
        return 1;
    }
    ll res = binpow(mult(x, x), pw / 2);
    if (pw & 1)
    {
        return mult(res, x);
    }
    return res;
}

// vector<pair<int, int>> nx = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

// const ll maxf = 2e6;

// ll fact[maxf], ifact[maxf];

// void precalc()
// {
//     fact[0] = 1;
//     for (int i = 1; i < maxf; ++i)
//     {
//         fact[i] = mult(i, fact[i - 1]);
//     }
//     ifact[maxf - 1] = binpow(fact[maxf - 1], mod - 2);
//     for (int i = maxf - 1; i > 0; --i)
//     {
//         ifact[i - 1] = mult(ifact[i], i);
//     }
//     assert(ifact[0] == 1);
// }

// ll C(int n, int k)
// {
//     if (n < k || k < 0)
//         return 0;
//     return mult(fact[n], mult(ifact[n - k], ifact[k]));
// }

// ll P(int n, int k)
// {
//     if (k <= 0)
//         return 0;
//     return C(n + k - 1, k - 1);
// }

// struct pt
// {
//     ll x, y;
//     pt operator-(pt r) const
//     {
//         return {x - r.x, y - r.y};
//     }
//     pt operator+(pt r) const
//     {
//         return {x + r.x, y + r.y};
//     }
//     ll dist2(pt r) const
//     {
//         return (x - r.x) * (x - r.x) + (y - r.y) * (y - r.y);
//     }
// };
// struct line
// {
//     ll a, b, c;
//     line(ll a_, ll b_, ll c_) : a(a_), b(b_), c(c_)
//     {
//     }
//     line(const pt &f, const pt &s)
//         : a(f.y - s.y), b(s.x - f.x), c(-a * f.x - b * f.y) {}
//     ld val(const pt &p) const { return a * p.x + b * p.y + c; }
// };
// ld operator*(const pt &a, const pt &b) { return a.x * b.x + a.y * b.y; }
// ld operator^(const pt &a, const pt &b) { return a.x * b.y - b.x * a.y; }

// bool isCw(const pt &a, const pt &b, const pt &c) { return ((b - a) ^ (c - a)) < 0; }
// bool isCcw(const pt &a, const pt &b, const pt &c) { return 0 < ((b - a) ^ (c - a)); }

// struct pt
// {
//     ll x, y;

//     ll dst2(pt A)
//     {
//         return (A.x - x) * (A.x - x) + (A.y - y) * (A.y - y);
//     }
// };

// const int maxn = (1 << 20);
// int a[maxn], sum[maxn];

// const int maxc = 22;
// int C[maxc][maxc];

// typedef bitset<100> bs;

// vector<char> is_prime;
// const int mxpr = 5e5;

// void prec()
// {
//     is_prime.assign(mxpr, true);
//     is_prime[0] = false;
//     is_prime[1] = false;
//     forn(i, mxpr)
//     {
//         if (is_prime[i])
//         {
//             for (int j = 2; j * i < mxpr; ++j)
//             {
//                 is_prime[j * i] = false;
//             }
//         }
//     }
// }

const ll maxn = 404;
const ll inf = 1e9;

mt19937 gen(0);

struct SegTr
{
    vector<ll> tr;

    SegTr(ll n) : tr(4 * n)
    {
    }

    void Set(ll i, ll val, ll tv, ll l, ll r)
    {
        if (l > i || r <= i)
        {
            return;
        }
        if (l + 1 == r)
        {
            tr[tv] = val;
            return;
        }
        ll md = (l + r) / 2;
        Set(i, val, 2 * tv, l, md);
        Set(i, val, 2 * tv + 1, md, r);
        tr[tv] = tr[2 * tv] + tr[2 * tv + 1];
    }

    ll Get(ll p, ll v, ll l, ll r)
    {
        if (p <= l)
        {
            return 0;
        }
        if (p >= r)
            return tr[v];
        ll md = (l + r) / 2;
        return Get(p, 2 * v, l, md) + Get(p, 2 * v + 1, md, r);
    }
};

void Solve()
{
    int n, m;
    cin >> n >> m;
    vector<tuple<int, int, int>> segs;
    int i0 = -1;
    for (int i = 0; i < m; ++i)
    {
        int l, r;
        cin >> l >> r;
        l--;
        segs.push_back({l, r, i});

        if (l == 0 && r == n)
        {
            i0 = i;
        }
    }
    if (i0 >= 0)
    {
        cout << "1\n";
        forn(i, m)
        {
            if (i == i0)
            {
                cout << "1 ";
            }
            else
            {
                cout << "0 ";
            }
        }
        return;
    }
    sort(segs.begin(), segs.end(), [](tuple<int, int, int> l, tuple<int, int, int> r)
         { 
            if (get<0>(l) != get<0>(r) ) 
                return get<0>(l) < get<0>(r);
            return  get<1>(l) >get<1>(r); });
    // int last = -1;

    forn(j, m)
    {
        if (j > 0)
        {
            if (get<1>(segs[j]) <= get<1>(segs[j - 1]))
            {
                int i1 = get<2>(segs[j]);
                int i2 = get<2>(segs[j - 1]);
                cout << "2\n";
                forn(i, m)
                {
                    if (i != i1 && i != i2)
                    {
                        cout << "0 ";
                    }
                    else if (i == i1)
                    {
                        cout << "2 ";
                    }
                    else
                    {

                        cout << "1 ";
                    }
                }
                return;
            }
        }
    }
    if (get<1>(segs[0]) <= get<0>(segs[m - 1]))
    {
        int i1 = get<2>(segs[m - 1]);
        int i2 = get<2>(segs[0]);
        cout << "2\n";
        forn(i, m)
        {
            if (i != i1 && i != i2)
            {
                cout << "0 ";
            }
            else if (i == i1)
            {
                cout << "2 ";
            }
            else
            {

                cout << "2 ";
            }
        }
        return;
    }

    if (get<0>(segs[0]) == 0 && get<1>(segs[m - 1]) == n)
    {
        int i1 = get<2>(segs[m - 1]);
        int i2 = get<2>(segs[0]);
        cout << "2\n";
        forn(i, m)
        {
            if (i != i1 && i != i2)
            {
                cout << "0 ";
            }
            else if (i == i1)
            {
                cout << "1 ";
            }
            else
            {

                cout << "1 ";
            }
        }
        return;
    }

    if (m < 3)
    {
        cout << "-1\n";
        return;
    }

    int i1 = get<2>(segs[0]);
    int i2 = get<2>(segs[1]);
    int i3 = get<2>(segs[2]);

    cout << "3\n";
    forn(i, m)
    {
        if (i != i1 && i != i2 && i != i3)
        {
            cout << "0 ";
        }
        else if (i == i2)
        {
            cout << "1 ";
        }
        else
        {
            cout << "2 ";
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef ONPC
    freopen("input.txt", "r", stdin);
#endif
    cout << setprecision(15);
    // prec();
    int q = 1;
    // cin >> q;
    while (q--)
    {
        Solve();
    }
    return 0;
}

Submission Info

Judge Result