打卡信奥刷题（3344）用C++实现信奥题 P9446 [ICPC 2021 WF] Prehistoric Programs

P9446 [ICPC 2021 WF] Prehistoric Programs题目描述考古学家在 Alutila 洞穴的深层发现了令人兴奋的粘土板。除了两个似乎描述嵌套结构的符号类似于 LISP 中的开括号和闭括号外没有人能够破译粘土板上的文字。难道几千年前人类就已经在编写程序了吗综合来看这些粘土板似乎描述了一项伟大的作品——可能是一个程序或者是一部史诗甚至是税务记录不出所料经过这么长时间粘土板已经处于无序状态。你的任务是将它们排列成一个序列使得结果作品具有正确嵌套的括号结构。仅考虑开括号和闭括号一个正确嵌套的结构要么是()()()或者(A)(A)(A)其中AAA是一个正确嵌套的结构或者ABABAB其中AAA和BBB是正确嵌套的结构。输入格式输入的第一行包含一个整数nnn(1≤n≤1061 \leq n \leq 10^61≤n≤106)表示粘土板的数量。接下来的nnn行中的每一行描述一个粘土板并包含一个非空的开括号和闭括号字符串与嵌套结构无关的符号被省略。字符串按照它们在输入中出现的顺序从111到nnn编号。输入中最多包含10710^7107个括号。输出格式输出一个从111到nnn的数字排列使得按此顺序连接字符串后形成一个正确嵌套的结构。如果存在多个排列满足条件任何一个都可以接受。如果没有这样的排列输出impossible\texttt{impossible}impossible。输入输出样例 #1输入 #12 ())())() ((()输出 #12 1输入输出样例 #2输入 #25 ( )) (( )) (输出 #21 5 3 4 2输入输出样例 #3输入 #32 (( )输出 #3impossible说明/提示题面翻译由 ChatGPT-4o 提供。C实现#includebits/stdc.husingnamespacestd;#definedebug(i)coutCute_MKS i #definepiipairint,int#definemkp(a,b)make_pair(a,b)constintN1e610;structnode{intx,y,mn,p;booloperator(constnodex)const{returnmnx.mn;}}a[N];intans[N],n;intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(inti1;in;i){string s;inttop0;a[i].xa[i].y0;a[i].pi;cins;for(intj0;js.length();j){if(s[j])){if(!top)a[i].x;elsetop--;}elsetop;}a[i].ytop;a[i].mnmin(a[i].x,a[i].y);}intl1,rn;sort(a1,an1);for(inti1;in;i){if(a[i].mna[i].x)ans[l]a[i].p;elseans[r--]a[i].p;}sort(a1,an1,[](node x,node y)-bool{returnx.py.p;});intsum0;for(inti1;in;i){if(a[ans[i]].xsum0){coutimpossible;return0;}suma[ans[i]].x-a[ans[i]].y;}if(a[ans[n]].y0||sum!0){coutimpossible;return0;}for(inti1;in;i)coutans[i]\n;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容