結果

問題 No.1328 alligachi-problem
ユーザー startcppstartcpp
提出日時 2021-01-04 04:47:57
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,796 bytes
コンパイル時間 1,262 ms
コンパイル使用メモリ 82,872 KB
実行使用メモリ 9,428 KB
最終ジャッジ日時 2024-04-22 01:39:50
合計ジャッジ時間 7,751 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 3 ms
5,376 KB
testcase_07 WA -
testcase_08 AC 2 ms
5,376 KB
testcase_09 WA -
testcase_10 AC 97 ms
6,760 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 93 ms
6,604 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 97 ms
6,760 KB
testcase_24 AC 98 ms
7,776 KB
testcase_25 AC 98 ms
9,428 KB
testcase_26 AC 102 ms
8,468 KB
testcase_27 AC 106 ms
8,596 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int n;
char c[200000], x[200000]; int y[200000];
vector<P> balls[2][2];

bool check(vector<int> 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<int> 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<int> 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<int> ans;
	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 (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++;
		}
		else if (x[b] == 'B') {
			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++;
		}
		else {
			ans.push_back(ids[0][i]);
			i++;
		}
	}
	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;
}
0