BOJ 25320 - SCV 체인

BOJ 25320 - SCV 체인

무조건 CHAIN 을 끼워넣어야 하는 경우는 A A 처럼 있거나 B B 처럼있거나 제일 뒤가 A인 경우이다.

그리디하게 가장 끼워넣을 수 있는 것 중 작은 것을 끼워넣는다.

이 가장 작은것이 없다면 NO 를 출력한다.

마지막에 안쓰이고 남은 숫자들은 안쓰이고 남은 숫자 중 가장 작은 것보다 작은 것이 있는 적당한 곳에 계속 이어붙이면 된다.

void fail() {  
   cout << "NO";  
   exit(0);  
}  
struct seg_tree {  
   int N;  
   vi tree;  
   seg_tree(int N) : N(N) {  
      int size = 1 << int(ceil(log2(N)) + 1);  
      tree.resize(size);  
   }  
  
   void update(int n, int nl, int nr, int i, int v) {  
      if (i > nr || i < nl) return;  
      if (nl == nr) {  
         tree[n] = v;  
         return;  
      }  
      int m = (nl + nr) >> 1;  
      update(n * 2, nl, m, i, v);  
      update(n * 2 + 1, m + 1, nr, i, v);  
      tree[n] = tree[n * 2] + tree[n * 2 + 1];  
   }  
   int query(int n, int nl, int nr, int l, int r) {  
      if (r < nl || l > nr) return 0;  
      if (nl >= l && nr <= r) return tree[n];  
  
      int m = (nl + nr) >> 1;  
      return query(n * 2, nl, m, l, r) + query(n * 2 + 1, m + 1, nr, l, r);  
   }  
   int query(int lower) {  
      if (lower >= N) return -1;  
      int l = lower, r = N - 1, ret = -1;  
  
      while (l <= r) {  
         int m = (l + r) >> 1;  
         if (query(1, 0, N - 1, lower, m) < m - lower + 1) {  
            ret = m;  
            r = m - 1;  
         } else {  
            l = m + 1;  
         }  
      }  
      return ret;  
   }  
};  
  
void solve() {  
   int n, m;  
   cin >> n >> m;  
   vector<array<int, 3>> his;  
   seg_tree seg(2 * n);  
   vi used(n * 2);  
   for (int i = 0; i < m; i++) {  
      string a, b;  
      int k;  
      cin >> a >> b >> k;  
      k--;  
      his.pb({  
                a == "A" ? 1 : 2,  
                b == "BLOCK" ? 1 : 2,  
                k,  
             });  
      seg.update(1, 0, 2 * n - 1, k, 1);  
      used[k] = 1;  
   }  
   vector<vector<array<int, 3>>> ans(m);  
   for (int i = 0; i < m; i++) ans[i].pb(his[i]);  
   for (int i = 0; i < m - 1; i++) {  
      if (his[i][0] == his[i + 1][0]) {  
         int nxt = seg.query(his[i][2] + 1);  
         if (nxt == -1) fail();  
         seg.update(1, 0, 2 * n - 1, nxt, 1);  
         ans[i].pb({3 - his[i][0], 2, nxt});  
         used[nxt] = 1;  
      }  
   }  
   vi remain;  
   for (int i = 0; i < 2 * n; i++) if (!used[i]) remain.pb(i);  
  
   auto print = [&]() {  
      cout << "YES\n";  
      for (int i = 0; i < m; i++) {  
         for (auto &[a, b, c]: ans[i]) {  
            cout << (a == 1 ? 'A' : 'B') << ' ' << (b == 1 ? "BLOCK" : "CHAIN") << ' ' << c + 1 << endl;  
         }  
      }  
   };  
  
   if (!sz(remain)) {  
      print();  
      return;  
   }  
   // 가장 뒤가 A로 끝날 경우, B를 무조건 붙여줘야 함  
   if (ans[m - 1].back()[0] == 1) {  
      if (remain.back() < ans[m - 1].back()[2]) fail();  
  
      int j = ubi(remain, ans[m - 1].back()[2]);  
  
      ans[m - 1].pb({2, 2, remain[j]});  
  
      remain.erase(remain.begin() + j);  
   }  
  
   if (!sz(remain)) {  
      print();  
      return;  
   }  
  
   int mn_value = 1e9, mn_idx = -1;  
   for (int i = 0; i < m; i++) {  
      if (ans[i].back()[2] < mn_value) {  
         mn_idx = i, mn_value = ans[i].back()[2];  
      }  
   }  
  
   // 남은 수들을 붙일 데가 없다면,  
   if (mn_value > remain[0]) fail();  
  
   for (int i: remain) ans[mn_idx].pb({3 - ans[mn_idx].back()[0], 2, i});  
   print();  
}