//「色, 値」のタグがついたボールを並べ替える。色 = 〇, ●で説明. 色:タグと記述。 //1. 〇:〇のボールは相対順序が決まる。値昇順じゃないといけない。 //2. 1.で作った列に〇:●を入れる方法が決まる。〇:●の相対順序も値昇順。 //3. 別の場所に、●:〇, ●:●の並びを作れる。これも1. 2.と同様の手順。 //4. 2.の列に3.の列の要素を左から挿入していくことを考えると、●:〇は〇の数, ●:●は //〇:●に書かれた値から入れる箇所を決定できる。 //ここまでは割と簡単(3.がポイントっぽい)。実装では矛盾を丁寧に弾く必要がある。 #include #include #include #define rep(i, n) for(i = 0; i < n; i++) using namespace std; typedef pair P; //cnt, id int n; char c[200000], x[200000]; int y[200000]; vector

balls[2][2]; bool check(vector p) { int cnt[2] = {0}; for (int i = 0; i < p.size(); i++) { int id = p[i]; int idc = (c[id] == 'B') ? 0 : 1; int idx = (x[id] == 'B') ? 0 : 1; if (cnt[idx] != y[id]) return false; cnt[idc]++; } return true; } void print(vector ans) { for (int i = 0; i < ans.size(); i++) { cout << ans[i] + 1; if (i + 1 < ans.size()) cout << " "; } cout << endl; } int main() { int i, j, k; cin >> n; rep(i, n) { cin >> c[i] >> x[i] >> y[i]; int idc = (c[i] == 'B') ? 0 : 1; int idx = (x[i] == 'B') ? 0 : 1; balls[idc][idx].push_back(P(y[i], i)); } rep(i, 2) rep(j, 2) sort(balls[i][j].begin(), balls[i][j].end()); vector ids[2]; rep(i, 2) { k = 0; rep(j, balls[i][i].size()) { for (; k < balls[i][i][j].first - j; k++) { if (k >= balls[i][!i].size()) { cout << "No" << endl; return 0; } ids[i].push_back(balls[i][!i][k].second); } ids[i].push_back(balls[i][i][j].second); } for (; k < balls[i][!i].size(); k++) ids[i].push_back(balls[i][!i][k].second); } //rep(i, 2) print(ids[i]); vector upper[2]; rep(i, 2) { rep(j, ids[i].size()) { int idx = (x[ids[i][j]] == 'B') ? 0 : 1; if (idx != i) upper[i].push_back(y[ids[i][j]]); } } vector ans; int upi = 0, upj = 0; i = 0; j = 0; while (i < ids[0].size() && j < ids[1].size()) { int a = ids[0][i]; int b = ids[1][j]; if (x[a] == 'R') { if (j > y[a]) { cout << "No" << endl; return 0; } if (y[a] > ids[1].size()) { cout << "No" << endl; return 0; } while (j < y[a]) { ans.push_back(ids[1][j]); j++; } ans.push_back(ids[0][i]); i++; upi++; } else if (x[b] == 'B') { if (i > y[b]) { cout << "No" << endl; return 0; } if (y[b] > ids[0].size()) { cout << "No" << endl; return 0; } while (i < y[b]) { ans.push_back(ids[0][i]); i++; } ans.push_back(ids[1][j]); j++; upj++; } else { if (upj >= upper[1].size() || i < upper[1][upj]) { ans.push_back(ids[0][i]); i++; } else { ans.push_back(ids[1][j]); j++; } } } while (i < ids[0].size()) { ans.push_back(ids[0][i]); i++; } while (j < ids[1].size()) { ans.push_back(ids[1][j]); j++; } //if (!check(ans)) { cout << "No" << endl; return 0; } cout << "Yes" << endl; print(ans); return 0; }