結果

問題 No.1328 alligachi-problem
ユーザー startcppstartcpp
提出日時 2021-01-04 05:02:29
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,122 bytes
コンパイル時間 928 ms
コンパイル使用メモリ 83,468 KB
実行使用メモリ 9,864 KB
最終ジャッジ日時 2024-04-22 01:56:20
合計ジャッジ時間 6,269 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 2 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 100 ms
6,764 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 96 ms
6,892 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 101 ms
6,888 KB
testcase_24 AC 105 ms
7,904 KB
testcase_25 AC 100 ms
8,916 KB
testcase_26 AC 104 ms
9,864 KB
testcase_27 AC 100 ms
9,728 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> 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<int> 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 (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 (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[0][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;
}
0