Submission #62238726

Source Code Expand

import sys

input = sys.stdin.readline

N = int(input())
A = input().rstrip()


def f(l, r):
    if l + 1 == r:
        return A[l], 1
    m1 = (2 * l + r) // 3
    m2 = (l + 2 * r) // 3
    val1, cnt1 = f(l, m1)
    val2, cnt2 = f(m1, m2)
    val3, cnt3 = f(m2, r)

    if val1 == val2 == val3:
        return val1, cnt1 + cnt2 + cnt3 - max(cnt1, cnt2, cnt3)
    elif val1 == val2:
        return val1, min(cnt1, cnt2)
    elif val1 == val3:
        return val1, min(cnt1, cnt3)
    elif val2 == val3:
        return val2, min(cnt2, cnt3)


print(f(0, 3**N)[1])

Submission Info

Submission Time
Task E - Hierarchical Majority Vote
User sotanishy
Language Python (PyPy 3.10-v7.3.12)
Score 450
Code Size 591 Byte
Status AC
Exec Time 176 ms
Memory 86740 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 450 / 450
Status
AC × 2
AC × 32
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt
All 00_sample_01.txt, 00_sample_02.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 02_handmade_01.txt, 02_handmade_02.txt, 02_handmade_03.txt, 02_handmade_04.txt, 02_handmade_05.txt, 02_handmade_06.txt, 02_handmade_07.txt, 02_handmade_08.txt, 02_handmade_09.txt, 02_handmade_10.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 61 ms 76676 KiB
00_sample_02.txt AC 60 ms 76420 KiB
01_random_01.txt AC 74 ms 80804 KiB
01_random_02.txt AC 176 ms 86356 KiB
01_random_03.txt AC 61 ms 76724 KiB
01_random_04.txt AC 172 ms 86100 KiB
01_random_05.txt AC 77 ms 82276 KiB
01_random_06.txt AC 168 ms 86516 KiB
01_random_07.txt AC 87 ms 82484 KiB
01_random_08.txt AC 172 ms 86620 KiB
01_random_09.txt AC 61 ms 76632 KiB
01_random_10.txt AC 174 ms 86396 KiB
01_random_11.txt AC 61 ms 76676 KiB
01_random_12.txt AC 158 ms 86072 KiB
01_random_13.txt AC 61 ms 76592 KiB
01_random_14.txt AC 174 ms 86488 KiB
01_random_15.txt AC 71 ms 81100 KiB
01_random_16.txt AC 170 ms 86248 KiB
01_random_17.txt AC 74 ms 81320 KiB
01_random_18.txt AC 167 ms 86740 KiB
01_random_19.txt AC 60 ms 76428 KiB
01_random_20.txt AC 170 ms 86516 KiB
02_handmade_01.txt AC 149 ms 86336 KiB
02_handmade_02.txt AC 153 ms 86460 KiB
02_handmade_03.txt AC 150 ms 86092 KiB
02_handmade_04.txt AC 150 ms 86080 KiB
02_handmade_05.txt AC 150 ms 86468 KiB
02_handmade_06.txt AC 155 ms 86400 KiB
02_handmade_07.txt AC 152 ms 86200 KiB
02_handmade_08.txt AC 154 ms 86248 KiB
02_handmade_09.txt AC 156 ms 86100 KiB
02_handmade_10.txt AC 159 ms 86244 KiB