Submission #2180069

---

Source Code Expand

<?php
fscanf(STDIN, "%d %d", $n, $k);
fscanf(STDIN, "%s", $s);

$chars = [];
for ($i = 0; $i < $n; $i++) {
	$chars["" . $i] = $s[$i];
}
if ($k < 2) {
	echo $s, "\n";
	return;
}

$before = $chars;
sort($chars);

$score = diff($before, $chars);
if ($score <= $k) {
	echo implode($chars), "\n";
	return;
}

while ($score > $k) {
	//echo implode($chars), "\n";
	$memo = [];
	for ($i = $n; $i > 0; $i--) {
		if ($before[$i] === $chars[$i]) {
			continue;
		}
		for ($j = $i - 1; $j > 0; $j--) {
			if ($chars[$j] === $chars[$i]) {
				continue;
			}
			if ($before[$i] === $chars[$j] || $before[$j] === $chars[$i]) {
				if (!isset($memo[$j])) {
					$memo[$j] = [$i, $j];
				}
				break;
			}
		}
	}
	krsort($memo);
	$first = array_shift($memo);
	//echo "Score:" . $score, "\n";
	//echo json_encode($first), "\n";
	$i = $first[0];
	$j = $first[1];

	if ($before[$i] === $chars[$j] && $before[$j] === $chars[$i]) {
		$score--;
	}
	$score--;
	$temp = $chars[$i];
	$chars[$i] = $chars[$j];
	$chars[$j] = $temp;
}
//echo implode($chars), "\n";
$chars = siage($before, $chars);
echo implode($chars), "\n";

function diff($a, $b)
{
	$l = count($a);
	$score = 0;
	for ($i = 0; $i < $l; $i++) {
		if ($a[$i] !== $b[$i]) {
			$score++;
		}
	}
	return $score;
}

function siage($before, $after)
{
	$l = count($before);
	$memo = [];
	for ($i = 0; $i < $l; $i++) {
		if ($before[$i] !== $after[$i]) {
			$memo[$i] = $after[$i];
		}
	}
	$keys = array_keys($memo);
	asort($memo);
	foreach ($keys as $key) {
		$after[$key] = array_shift($memo);
	}
	//var_dump($memo);
	return $after;
}

Submission Info

Judge Result