{"kind":"task","effective_mode":"full","benchmark":{"kind":"benchmark","effective_mode":"full","slug":"hlce","formal_name":"Humanity's Last Code Exam","introduction":"Humanity's Last Code Exam evaluates problem solving and code generation using ICPC World Finals and IOI problems. The project describes 235 problems; this import selects its public ICPC dataset of 146 problems.","introduction_ja":"","introduction_en":"","category":"Category not supplied","task_count":null,"acquisition_status":"Acquisition status not supplied","official_url":"https://humanity-s-last-code-exam.github.io/website/","indexing_mode":"noindex","profile":{"resources":[],"task_format":"","scoring":"","metric":"","size":"","answer_access":"","license":"","citation":"","maintainer":"","released":"","why_hard":"","related":[]}},"task_id":"e32bbf5b-a1e6-5c94-81cf-24ad39654e73","task_key":"ICPC~2dWorld~2dFinals--examples--2021~5fH","task_revision_id":"3","upstream_id":"2021_H","short_description":"Prehistoric Programs","config":"ICPC-World-Finals","split":"examples","body":"{\"platform\":\"atcoder\",\"question_content\":\"## Problem Statement\\n\\nArchaeologists have discovered exciting clay tablets in deep layers of Alutila Cave. Nobody was able to decipher the script on the tablets, except for two symbols that seem to describe nested structures not unlike opening and closing parentheses in LISP. Could it be that humans wrote programs thousands of years ago?\\n\\nTaken together, the tablets appear to describe a great piece of work – perhaps a program, or an epic, or even tax records! Unsurprisingly, after such a long time, the tablets are in a state of disorder. Your job is to arrange them into a sequence so that the resulting work has a properly nested parenthesis structure. Considering only opening and closing parentheses, a properly nested structure is either:\\n\\n- `()`, or\\n- `(A)`, where \\\\(A\\\\) is a properly nested structure, or\\n- `AB`, where \\\\(A\\\\) and \\\\(B\\\\) are properly nested structures.\\n\\n## Input\\n\\nThe first line of input contains one integer \\\\(n\\\\) \\\\((1 \\\\leq n \\\\leq 10^6)\\\\), the number of tablets. Each of the remaining \\\\(n\\\\) lines describes a tablet and contains a non-empty string of opening and closing parentheses; symbols unrelated to the nesting structure are omitted. The strings are numbered from 1 to \\\\(n\\\\) in the order that they appear in the input. The input contains at most \\\\(10^7\\\\) parentheses.\\n\\n## Output\\n\\nOutput a permutation of the numbers from 1 to \\\\(n\\\\) such that concatenating the strings in this order results in a properly nested structure. If this happens for multiple permutations, any one of them will be accepted. If there is no such permutation, output `impossible` instead.\\n\\n## Sample Input 1\\n\\n```\\n2\\n())())()\\n((()\\n```\\n\\n## Sample Output 1\\n\\n```\\n2\\n1\\n```\\n\\n## Sample Input 2\\n\\n```\\n5\\n(\\n))\\n((\\n))\\n(\\n```\\n\\n## Sample Output 2\\n\\n```\\n1\\n5\\n3\\n2\\n4\\n```\\n\\n## Sample Input 3\\n\\n```\\n2\\n((\\n)\\n```\\n\\n## Sample Output 3\\n\\n```\\nimpossible\\n```\",\"question_title\":\"Prehistoric Programs\"}","display_format":"text","language":"","answer_status":"published","assets":[],"source_url":"https://humanity-s-last-code-exam.github.io/website/","history":"initial import","indexing_mode":"noindex","subproblems":[],"grids":[]}