Submission #7404695


Source Code Expand

Copy
<?php
fscanf(STDIN, '%d %d', $n, $k);
fscanf(STDIN, '%s', $s);
$lh = $rh = 0;
$top = 0;
$top_s = $s[$top];
$lq = new SplPriorityQueue;
$rq = new SplPriorityQueue;
while($top < $n) {
    if ($top_s === 'L') $next_s = 'R';
    else $next_s = 'L';
    $next_top = strpos($s, $next_s, $top);
    if ($next_top === false) $next_top = $n;
    $p = $next_top - $top + 1;
    if ($top === 0) $p--;
    if ($next_top === $n) $p--;
    if ($top_s === 'L') {
        $lq->insert([$top, $next_top - $top], $p);
        $lh += $next_top - $top - 1;
    } else {
        $rq->insert([$top, $next_top - $top], $p);
        $rh += $next_top - $top - 1;
    }
    $top_s = $next_s;
    $top = $next_top;
}
if ($lh >= $rh) $lf = true;
else $lf = false;
$i = 0;
while ($i < $k) {
    if ($lf) {
        if ($rq->count() <= 0) break;
        $x = $rq->extract();
        $s = substr_replace($s, str_repeat('L', $x[1]), $x[0], $x[1]);
    } else {
        if ($lq->count() <= 0) break;
        $x = $lq->extract();
        $s = substr_replace($s, str_repeat('R', $x[1]), $x[0], $x[1]);
    }
    $i++;
}
$ans = 0;
for ($i = 0; $i < $n - 1; $i++) {
    if ($s[$i + 1] === $s[$i]) $ans++;
}
echo $ans . PHP_EOL;

Submission Info

Submission Time
Task D - Face Produces Unhappiness
User hideyuk1
Language PHP7 (7.0.15)
Score 0
Code Size 1233 Byte
Status
Exec Time 943 ms
Memory 86520 KB

Test Cases

Set Name Score / Max Score Test Cases
All 0 / 400 sample_01, sample_02, sample_03, testcase_01, testcase_02, testcase_03, testcase_04, testcase_05, testcase_06, testcase_07, testcase_08, testcase_09, testcase_10, testcase_11, testcase_12, testcase_13, testcase_14, testcase_15, testcase_16, testcase_17, testcase_18, testcase_19, testcase_20, testcase_21
Sample 0 / 0 sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
sample_01 12 ms 4728 KB
sample_02 9 ms 4604 KB
sample_03 9 ms 4732 KB
testcase_01 116 ms 29176 KB
testcase_02 225 ms 45560 KB
testcase_03 207 ms 43512 KB
testcase_04 223 ms 45560 KB
testcase_05 16 ms 8696 KB
testcase_06 81 ms 45560 KB
testcase_07 21 ms 10744 KB
testcase_08 225 ms 45560 KB
testcase_09 943 ms 35320 KB
testcase_10 221 ms 45560 KB
testcase_11 225 ms 45560 KB
testcase_12 14 ms 6648 KB
testcase_13 123 ms 45560 KB
testcase_14 343 ms 86520 KB
testcase_15 272 ms 86520 KB
testcase_16 348 ms 86520 KB
testcase_17 130 ms 86520 KB
testcase_18 18 ms 4604 KB
testcase_19 18 ms 4604 KB
testcase_20 9 ms 4604 KB
testcase_21 18 ms 4604 KB