Ravintola

// B
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

struct Q {
  int a, b, c, i;
};

struct acmp {
  bool operator()(const Q &a, const Q &b) const {
    return a.a < b.a;
  }
};

struct ibcmp {
  bool operator()(const Q &a, const Q &b) const {
    return a.b > b.b;
  }
};

struct icmp {
  bool operator()(const Q &a, const Q &b) const {
    return a.i < b.i;
  }
};

int main() {
  int n;
  cin >> n;
  vector<Q> v(n);
  {
    int i = 0;
    for (auto &q : v)
      cin >> q.a >> q.b, q.i = i++;
  }
  
  sort(v.begin(), v.end(), acmp());
    
  priority_queue<Q, vector<Q>, ibcmp> pq;
  set<int> f;
  int tc = 0;
  for (auto &q : v) {
    while (!pq.empty() && pq.top().b <= q.a) {
      f.insert(pq.top().c);
      pq.pop();
    }
    
    if (f.empty())
      f.insert(++tc);
    
    q.c = *f.begin();
    f.erase(f.begin());
    pq.push(q);
  }
  
  sort(v.begin(), v.end(), icmp());
  cout << tc << '\n';
  for (auto &q : v) {
    cout << q.c << '\n';
  }
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED