履歴クエリ対応のバージョン付きキー・バリューストアを実装する

import sys import bisect def solve(): """ 標準入力からコマンドを読み込み、標準出力に結果を書き込むバージョン管理されたキーバリューストアを実装します。 """ try: n_str = sys.stdin.readline() if not n_str: return n = int(n_str.strip()) except (ValueError, IndexError): return # メインのデータ構造。 # 各キーをその履歴状態のリストにマッピングする辞書。 # 各状態はタプル: (バージョン, 値) です。 # 各キーのリストはバージョンでソートされた状態に保たれます。 # 値 None は削除を表します。 store = {} global_version = 0 for _ in range(n): line = sys.stdin.readline() if not line: continue parts = line.strip().split() command = parts[0] if command == "SET": # 新しいバージョンを作成して、キーを値で作成または上書きします。 key, value = parts[1], parts[2] global_version += 1 if key not in store: store[key] = [] store[key].append((global_version, value)) elif command == "DELETE": # キーを削除し、新しいバージョンを作成します。 # キーが存在しない場合でも適用されます。 key = parts[1] global_version += 1 if key not in store: store[key] = [] store[key].append((global_version, None)) elif command == "GET": # キーの現在の値を返します。 key = parts[1] if key not in store or not store[key]: print("NULL") else: # 履歴リストの最後の項目が現在の状態です。 _version, value = store[key][-1] print(value if value is not None else "NULL") elif command == "GET_VERSION": # 特定の履歴バージョンでのキーの値を返します。 key, version_str = parts[1], parts[2] version = int(version_str) if version <= 0 or version > global_version: print("INVALID_VERSION") elif key not in store or not store[key]: print("NULL") else: history = store[key] # 効率的な検索のために、バージョン番号のみのリストを作成します。 versions = [v for v, _val in history] # 要求されたバージョンを挿入するポイントを見つけます。 # bisect_right は、バージョンが順序を維持するように挿入されるインデックスを見つけます。 # これは、このインデックスの左側にあるすべての要素のバージョンが要求されたバージョン以下であることを意味します。 idx = bisect.bisect_right(versions, version) if idx == 0: # 要求されたバージョン以下の履歴バージョンはありません。 print("NULL") else: # 必要な状態は前のインデックス (idx - 1) にあります。 _v, value = history[idx - 1] print(value if value is not None else "NULL") elif command == "HISTORY": # キーのすべての履歴状態を返します。 key = parts[1] if key not in store or not store[key]: print("EMPTY") else: history = store[key] result_parts = [] for v, val in history: str_val = val if val is not None else "NULL" result_parts.append(f"{v}:{str_val}") print(",".join(result_parts)) if __name__ == "__main__": solve()

import sys from bisect import bisect_right def main(): input_data = sys.stdin.buffer.read().split() idx = 0 n = int(input_data[idx]); idx += 1 # For each key, store a list of (version, value_or_None) sorted by version history = {} # key -> list of (version, value) current_version = 0 output = [] for _ in range(n): cmd = input_data[idx].decode(); idx += 1 if cmd == 'SET': key = input_data[idx].decode(); idx += 1 value = input_data[idx].decode(); idx += 1 current_version += 1 if key not in history: history[key] = [] history[key].append((current_version, value)) elif cmd == 'DELETE': key = input_data[idx].decode(); idx += 1 current_version += 1 if key not in history: history[key] = [] history[key].append((current_version, None)) elif cmd == 'GET': key = input_data[idx].decode(); idx += 1 if key not in history or not history[key]: output.append('NULL') else: val = history[key][-1][1] output.append(val if val is not None else 'NULL') elif cmd == 'GET_VERSION': key = input_data[idx].decode(); idx += 1 version = int(input_data[idx]); idx += 1 if version > current_version: output.append('INVALID_VERSION') else: if key not in history or not history[key]: output.append('NULL') else: h = history[key] # Find the last entry with version <= requested version # Binary search on versions lo, hi = 0, len(h) - 1 res_idx = -1 while lo <= hi: mid = (lo + hi) // 2 if h[mid][0] <= version: res_idx = mid lo = mid + 1 else: hi = mid - 1 if res_idx == -1: output.append('NULL') else: val = h[res_idx][1] output.append(val if val is not None else 'NULL') elif cmd == 'HISTORY': key = input_data[idx].decode(); idx += 1 if key not in history or not history[key]: output.append('EMPTY') else: parts = [] for ver, val in history[key]: parts.append(f"{ver}:{val if val is not None else 'NULL'}") output.append(','.join(parts)) print('\n'.join(output)) main()