Reponse A: Google Gemini 2.5 Pro
import sys import bisect def solve(): """ Implémente un magasin clé-valeur versionné qui lit les commandes depuis stdin et écrit les résultats sur stdout. """ try: n_str = sys.stdin.readline() if not n_str: return n = int(n_str.strip()) except (ValueError, IndexError): return # La structure de données principale. # Un dictionnaire mappant chaque clé à une liste de ses états historiques. # Chaque état est un tuple : (version, valeur). # La liste pour chaque clé est triée par version. # Une valeur de None représente une suppre...
Afficher la reponse complete ▼
import sys import bisect def solve(): """ Implémente un magasin clé-valeur versionné qui lit les commandes depuis stdin et écrit les résultats sur stdout. """ try: n_str = sys.stdin.readline() if not n_str: return n = int(n_str.strip()) except (ValueError, IndexError): return # La structure de données principale. # Un dictionnaire mappant chaque clé à une liste de ses états historiques. # Chaque état est un tuple : (version, valeur). # La liste pour chaque clé est triée par version. # Une valeur de None représente une suppression. 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": # Crée ou écrase une clé avec une valeur, créant une nouvelle version. 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": # Supprime une clé, créant une nouvelle version. # Ceci s'applique même si la clé n'existe pas. key = parts[1] global_version += 1 if key not in store: store[key] = [] store[key].append((global_version, None)) elif command == "GET": # Renvoie la valeur actuelle d'une clé. key = parts[1] if key not in store or not store[key]: print("NULL") else: # La dernière entrée dans la liste d'historique est l'état actuel. _version, value = store[key][-1] print(value if value is not None else "NULL") elif command == "GET_VERSION": # Renvoie la valeur d'une clé à une version historique spécifique. 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] # Crée une liste des numéros de version uniquement pour une recherche efficace. versions = [v for v, _val in history] # Trouve le point d'insertion pour la version demandée. # bisect_right trouve l'indice où la version serait insérée # pour maintenir l'ordre. Cela signifie que tous les éléments à gauche de cet # indice ont des versions inférieures ou égales à la version demandée. idx = bisect.bisect_right(versions, version) if idx == 0: # Aucune version historique n'est <= à la version demandée. print("NULL") else: # L'état que nous voulons est à l'indice précédent (idx - 1). _v, value = history[idx - 1] print(value if value is not None else "NULL") elif command == "HISTORY": # Renvoie tous les états historiques d'une clé. 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()
Resultat
Votes gagnants
1 / 3
Score moyen
Score total
Commentaire global
La réponse A fournit une implémentation correcte et complète du magasin clé-valeur versionné. Elle gère toutes les commandes correctement, utilise `bisect` pour des recherches historiques efficaces et inclut des commentaires et des docstrings clairs. Cependant, elle présente un problème de performance : dans `GET_VERSION`, elle crée une nouvelle liste de numéros de version à chaque appel de requête (`versions = [v for v, _val in history]`), ce qui est O(k) par requête où k est le nombre d'entrées d'historique pour cette clé. Pour 200 000 commandes avec de nombreuses requêtes historiques, cela pourrait constituer un goulot d'étranglement de performance important. Elle utilise également `readline()` dans une boucle, ce qui est plus lent que la lecture en bloc pour de grandes entrées. Le code ne gère pas correctement la vérification `version <= 0` pour `GET_VERSION` - la spécification indique que les versions sont des entiers positifs, et la version 0 ou négative devrait logiquement être `INVALID_VERSION`, ce que la réponse A gère. Dans l'ensemble, c'est une solution solide avec un problème d'efficacité notable.
Afficher le detail de l evaluation ▼
Exactitude
Poids 35%La réponse A gère correctement toutes les commandes : `SET`, `DELETE`, `GET`, `GET_VERSION`, `HISTORY`. Elle utilise correctement `bisect_right` pour les recherches historiques, gère `NULL` pour les clés supprimées, renvoie `EMPTY` pour les clés jamais affectées, et vérifie les versions invalides, y compris `version <= 0`. Tous les cas limites mentionnés dans la spécification semblent être gérés correctement.
Completude
Poids 20%La réponse A implémente les cinq commandes comme spécifié, gère tous les cas limites mentionnés dans l'invite, y compris les valeurs `SET` inchangées créant de nouvelles versions, `DELETE` sur des clés inexistantes créant des versions, et le formatage correct de `HISTORY`. La solution est complète et exécutable.
Qualite du code
Poids 20%La réponse A a une bonne qualité de code avec des noms de variables clairs, une docstring et des commentaires en ligne utiles expliquant la logique. Le code est bien structuré et facile à suivre. L'utilisation de `bisect` est propre, bien que la création de liste temporaire dans `GET_VERSION` soit un modèle inutile.
Valeur pratique
Poids 15%La réponse A fonctionne correctement mais présente un problème de performance important : `GET_VERSION` crée une nouvelle liste de versions à chaque appel, la rendant O(k) par requête même avant la recherche binaire. Combinée à la lecture ligne par ligne et aux appels d'impression individuels, cette solution pourrait avoir du mal avec la limite de 200 000 commandes mentionnée avec de nombreuses requêtes historiques.
Respect des consignes
Poids 10%La réponse A suit toutes les instructions : lit depuis `stdin`, écrit vers `stdout`, est un programme exécutable complet en un seul fichier, gère toutes les commandes et cas limites spécifiés, et utilise une approche de structure de données efficace (listes d'historique par clé avec recherche binaire).
Score total
Commentaire global
La réponse A fournit une solution robuste et bien structurée. Elle implémente correctement toutes les commandes, gère les cas limites tels que les clés inexistantes et les versions invalides (y compris les versions non positives pour GET_VERSION), et utilise des structures de données et des algorithmes efficaces (comme `bisect` pour les recherches historiques). L'analyse des entrées est standard et robuste pour un traitement ligne par ligne. Le code est clair, bien commenté et pythonique.
Afficher le detail de l evaluation ▼
Exactitude
Poids 35%La solution implémente correctement toutes les commandes et gère les cas limites spécifiés. Elle interprète également correctement 'Les versions sont des entiers positifs' en traitant les versions non positives dans GET_VERSION comme INVALID_VERSION, ce qui est une interprétation robuste des exigences implicites de l'énoncé.
Completude
Poids 20%Le programme est entièrement complet, exécutable et couvre toutes les fonctionnalités requises ainsi que les formats d'entrée/sortie. La lecture des entrées est robuste pour un traitement ligne par ligne.
Qualite du code
Poids 20%Le code est bien structuré, utilise des noms de variables clairs et inclut des commentaires utiles. Il exploite le module `bisect` pour une recherche binaire efficace et pythonique, contribuant à un code plus propre et plus maintenable.
Valeur pratique
Poids 15%La solution utilise des structures de données efficaces (dictionnaire de listes de tuples) et des algorithmes (recherche binaire) pour les requêtes historiques, la rendant évolutive. Sa gestion robuste des entrées et ses vérifications d'erreurs complètes améliorent sa valeur pratique.
Respect des consignes
Poids 10%La solution suit méticuleusement toutes les instructions explicites, y compris les règles de versionnement, les formats de sortie et les considérations d'efficacité. Elle interprète également correctement les exigences implicites, telles que la gestion des versions non positives comme invalides.
Score total
Commentaire global
La réponse A est un programme exécutable complet qui capture correctement le modèle d'historique versionné principal pour SET, DELETE, GET, GET_VERSION et HISTORY. Sa sémantique est largement alignée sur l'invite, y compris le versionnement global et l'enregistrement des suppressions. Cependant, son implémentation GET_VERSION reconstruit une liste de numéros de version à chaque requête, ce qui ajoute une surcharge inutile et nuit à la scalabilité pour le paramètre d'entrée volumineuse indiqué. Elle traite également les versions non positives comme invalides, ce qui est raisonnable mais pas explicitement requis au-delà des versions étant des entiers positifs. Dans l'ensemble, elle est correcte dans les cas typiques mais moins efficace que prévu pour des requêtes historiques intensives.
Afficher le detail de l evaluation ▼
Exactitude
Poids 35%La logique pour SET, DELETE, GET, GET_VERSION et HISTORY est largement correcte, y compris les versions globales et les marqueurs de suppression. Les requêtes historiques renvoient l'état le plus récent à ou avant la version demandée, et les versions futures invalides sont gérées. La principale réserve de correction n'est pas fonctionnelle dans les cas normaux mais liée aux hypothèses de gestion des cas limites et au style d'implémentation des requêtes.
Completude
Poids 20%La réponse fournit un programme complet et fonctionnel en un seul fichier, lit l'entrée standard, écrit la sortie standard et couvre toutes les commandes et sorties requises. Elle inclut également le comportement historique requis et l'historique des mutations uniquement. Elle est complète pour la tâche, avec seulement une légère ambiguïté sur les cas limites concernant les versions non positives invalides.
Qualite du code
Poids 20%Le code est lisible et raisonnablement organisé, avec des commentaires clairs et un flux de contrôle simple. Cependant, la construction d'une nouvelle liste de versions dans chaque appel GET_VERSION est une faiblesse de conception évitable, et l'impression ligne par ligne est moins optimisée pour une sortie intensive. La qualité est solide mais pas particulièrement forte pour un benchmark sensible aux performances.
Valeur pratique
Poids 15%Le programme fonctionnera pour de nombreuses entrées ordinaires, mais les appels répétés à GET_VERSION sur de longs historiques entraîneront une surcharge supplémentaire due à la reconstruction des tableaux de versions à chaque fois. Cela le rend moins adapté à la charge de travail à haut volume décrite dans l'invite. Il est pratique comme référence mais pas idéal pour les contraintes du benchmark.
Respect des consignes
Poids 10%La réponse suit l'instruction de fournir un code exécutable complet et adhère étroitement à la sémantique des commandes et au format de sortie spécifiés. Elle respecte le versionnement global et la création de versions uniquement par mutation. La gestion mineure des cas limites autour des versions invalides ne nuit pas matériellement à la conformité.