小红的排列构造②【牛客tracker 每日一题】

小红的排列构造②时间限制1秒 空间限制256M知识点模拟网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小红定义一个仅由0 00和1 11两个字符构成的字符串s ss与一个长度为n nn的数组p pp为匹配当且仅当满足下列两点1.​若s i 1 s_i1si​1则数组{ p 1 , p 2 , … , p i } \{p_1,p_2,…,p_i\}{p1​,p2​,…,pi​}恰好构成一个排列2.​若s i 0 s_i0si​0则数组{ p 1 , p 2 , … , p i } \{p_1,p_2,…,p_i\}{p1​,p2​,…,pi​}无法构成一个排列。现在小红给出了一个长度为n nn的字符串s ss请你构造一个长度为n nn的排列p pp使得s ss与p pp匹配如果不存在这样的排列请输出− 1 −1−1。【名词解释】排列排列是由1 ∼ n 1∼n1∼n这n nn个整数按任意顺序组成的数组其中每个整数恰好出现一次。输入描述第一行输入一个整数n ( 1 ≦ n ≦ 10 5 ) n(1≦n≦10^5)n(1≦n≦105)表示字符串及排列的长度。第二行输入一个长度为n nn仅由0 00和1 11构成的字符串s ss。输出描述如果不存在满足条件的排列直接输出− 1 −1−1否则在一行上输出n nn个整数p 1 , p 2 , … , p n p_1,p_2,…,p_np1​,p2​,…,pn​表示你构造出的排列。如果存在多个满足条件的排列输出任意一个均可系统将自动判定其正确性。请注意自测运行功能可能因此返回错误结果请自行检查答案正确性。示例1输入3 001输出3 1 2说明对于这个样例由于s 0 0 s_00s0​0排列的前一项元素无法构成一个排列由于s 1 0 s_10s1​0排列的前两项元素无法构成一个排列由于s 2 1 s_21s2​1排列的前三项元素构成一个排列同时输出{ 2 , 3 , 1 } \{2,3,1\}{2,3,1}、{ 3 , 2 , 1 } \{3,2,1\}{3,2,1}等答案也都是合法的。示例2输入4 1110输出-1说明在此样例中若存在合法排列则前三位必须依次形成排列但第四位又要求整体不形成排列显然不可能因此答案为− 1 −1−1。解题思路本题核心依托前缀排列的核心性质求解前i个数构成1~i排列的充要条件是前缀最大值等于i。首先进行合法性判断字符串最后一位必须为1完整数组是1~n的排列否则直接输出-1。构造方案采用分段倒序填充策略遍历字符串将连续的0段与后续的1段合并为一个区间对区间内数字倒序填充。倒序填充能保证0位置的前缀最大值小于区间长度不构成排列到达1位置时前缀恰好为1~i的排列。算法时间复杂度O(n)高效适配n≤1e5的大数据约束。总结核心逻辑前缀排列的最大值判定规则分段倒序填充满足0/1匹配要求。关键操作最后一位为0直接判无解、分段倒序构造合法排列。效率保障线性遍历构造无冗余运算轻松处理十万级数据规模。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidsolve(){ll n;cinn;string s;cins;s s;vectorllans(n1);if(s[n]0){cout-1endl;return;}ll l1,r1;while(rn){if(s[r]0){while(s[r]0)r;for(ll ir;il;i--)couti ;lr1;r;}else{for(ll ir;il;i--)couti ;lr1;r;}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T1;//cinT;while(T--)solve();return0;}