結果

問題 No.2804 Fixer And Ratism
ユーザー NakLon131NakLon131
提出日時 2024-07-12 23:21:08
言語 Rust
(1.77.0)
結果
AC  
実行時間 61 ms / 2,000 ms
コード長 2,412 bytes
コンパイル時間 17,393 ms
コンパイル使用メモリ 396,248 KB
実行使用メモリ 8,580 KB
最終ジャッジ日時 2024-07-12 23:21:30
合計ジャッジ時間 20,588 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,812 KB
testcase_02 AC 1 ms
6,812 KB
testcase_03 AC 24 ms
6,940 KB
testcase_04 AC 15 ms
6,944 KB
testcase_05 AC 6 ms
6,944 KB
testcase_06 AC 23 ms
6,940 KB
testcase_07 AC 9 ms
6,940 KB
testcase_08 AC 8 ms
6,940 KB
testcase_09 AC 3 ms
6,944 KB
testcase_10 AC 7 ms
6,944 KB
testcase_11 AC 43 ms
6,940 KB
testcase_12 AC 29 ms
6,940 KB
testcase_13 AC 9 ms
6,944 KB
testcase_14 AC 27 ms
6,940 KB
testcase_15 AC 3 ms
6,940 KB
testcase_16 AC 24 ms
6,940 KB
testcase_17 AC 13 ms
6,944 KB
testcase_18 AC 33 ms
6,940 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 3 ms
6,940 KB
testcase_21 AC 52 ms
6,940 KB
testcase_22 AC 2 ms
6,944 KB
testcase_23 AC 59 ms
7,168 KB
testcase_24 AC 35 ms
7,296 KB
testcase_25 AC 61 ms
8,456 KB
testcase_26 AC 53 ms
7,296 KB
testcase_27 AC 36 ms
8,288 KB
testcase_28 AC 61 ms
8,580 KB
testcase_29 AC 50 ms
7,296 KB
testcase_30 AC 52 ms
8,232 KB
testcase_31 AC 36 ms
7,168 KB
testcase_32 AC 56 ms
7,296 KB
testcase_33 AC 1 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn main() {
    input!{
		n: usize, q: usize,
	}

	// 使用可能台数(可変)
	let mut nn = n;

	// 取り出す順(順序つき集合(値のみ))
	let mut bst = BTreeSet::new();
	
	// 在籍情報(人と値) (値と人)
	let mut mp = BTreeMap::new();
	let mut mp_rev = BTreeMap::new();

	// クエリ毎に処理
	for _ in 0..q {
		input!{
			nm: usize,
		}

		if nm == 1 {
			input!{
				s: String, t: usize,
			}

			// 人を追加
			bst.insert(t);
			mp.insert(s.clone(), t);
			mp_rev.insert(t, s.clone());
			
			// 定員を超えていたら取り出す
			dropout(nn, &mut mp, &mut mp_rev, &mut bst);
		}
		else if nm == 2 {

			input!{
				x: usize,
			}

			// 定員を減らす
			nn -= x;

			// 定員を超えていたら取り出す
			dropout(nn, &mut mp, &mut mp_rev, &mut bst);
		}
		else {
			input!{
				s: String, x: usize,
			}

			// 定員を増やす
			nn += x;

			// その人を優遇する 取り出して更新
			update_info(s, &mut mp, &mut mp_rev, &mut bst);

		}
	}

}

fn update_info(s: String, mp: &mut BTreeMap<String, usize>, mp_rev: &mut BTreeMap<usize, String>, st: &mut BTreeSet<usize>) {
	// if !mp.contains_key(&s) { return; }
	
	let mut now_t = *mp.get(&s).unwrap();
	mp.remove(&s);
	mp_rev.remove(&now_t);
	st.remove(&now_t);
	
	if now_t < 100_000 { now_t += 100_000; } // 1度のみ
	mp.insert(s.clone(), now_t);
	mp_rev.insert(now_t, s);
	st.insert(now_t);
}

fn dropout(n: usize, mp: &mut BTreeMap<String, usize>, mp_rev: &mut BTreeMap<usize, String>, st: &mut BTreeSet<usize>){
	let mut now_sz = mp.len();
	
	let mut ret = Vec::new();
	while now_sz > n {
		let (now_t, now_s) = mp_rev.pop_first().unwrap();
		st.pop_first();
		mp.remove(&now_s);

		ret.push((now_t % 100_000, now_s));
		now_sz -= 1;
	}
	ret.sort();
	
	for i in 0..ret.len() {
		println!("{}", ret[i].1);
	}
}

// const MOD17: usize = 1000000007;
// const MOD93: usize = 998244353;
// const INF: usize = 1 << 60;
// let dx = vec![!0, 0, 1, 0]; // 上左下右
// let dy = vec![0, !0, 0, 1]; // 上左下右
// let d = vec!{(!0, 0), (0, !0), (1, 0), (0, 1)}; // 上左下右

#[allow(unused)]
use proconio::{input, marker::Chars, marker::Usize1};

#[allow(unused)]
use std::{
	mem::swap,
	cmp::min, cmp::max,
	cmp::Reverse,
	collections::HashSet, collections::BTreeSet,
	collections::HashMap, collections::BTreeMap,
	collections::BinaryHeap,
	collections::VecDeque,
	iter::FromIterator,
};
0