QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#66054 | #5108. Prehistoric Programs | rumen_m# | WA | 97ms | 4136kb | C++14 | 2.6kb | 2022-12-06 03:00:39 | 2022-12-06 03:00:41 |
Judging History
answer
# include <bits/stdc++.h>
const long long MAXN = 1e6+5;
using namespace std;
struct ww
{
int id;
int ends;
int nms;
};
ww seq[MAXN];
bool cmp(ww i, ww j)
{
if(i.nms >= 0)
{
if( j.nms < 0) return true;
return i.ends >= j.ends;
}
if(j.nms >= 0) return false;
if(i.ends > 0)
{
if(j.ends <= 0) return true;
return i.ends <= j.ends;
}
if(j.ends > 0) return false;
return i.nms >= j.nms;
}
queue <int> ans;
vector <pair <int,int> > a,b;
priority_queue <pair <int,int> > pq;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
string s;
int i,j;
cin>>n;
int currD=0;
for(i = 1; i <= n; i++)
{
cin>>s;
seq[i].id= i;
seq[i].nms = 0;
seq[i].ends = 0;
for(char ch:s)
{
if(ch=='(')
{
seq[i].ends++;
}else
seq[i].ends--;
seq[i].nms = min(seq[i].nms,seq[i].ends);
}
if(seq[i].nms >= 0)
{
currD += seq[i].ends;
ans.push(i);
}else
if(seq[i].ends > 0)
a.push_back({-seq[i].nms,i});
else
b.push_back({seq[i].ends-seq[i].nms,i});
}
// sort(seq+1,seq+n+1,cmp);
sort(a.begin(),a.end());
for(i =0; i <a.size(); i++)
{
int curr= a[i].second;
// cout<<curr<<endl;
while(!pq.empty() && currD < seq[curr].nms)
{
int x = pq.top().second;
pq.pop();
currD += seq[x].ends;
ans.push(x);
}
// cout<<curr << " "<<seq[curr].nms<<" "<<currD<<endl;
if(currD < seq[curr].nms){cout<<"impossible\n";return 0;}
pq.push({seq[curr].ends,curr});
}
while(!pq.empty())
{
int x = pq.top().second;
pq.pop();
currD += seq[x].ends;
ans.push(x);
}
sort(b.begin(),b.end());
for(i = b.size()-1; i >=0; i--)
{
int curr = b[i].second;
if(currD < seq[curr].nms){cout<<"impossible\n";return 0;}
currD += seq[curr].ends;
ans.push(curr);
}
/* for(i =1; i <= n; i++)
{
cout<<seq[i].id<<endl;
if(currD + seq[i].nms < 0){cout<<"impossible\n";return 0;}
currD+=seq[i].ends;
}*/
if(currD!=0){cout<<"impossible\n";return 0;}
while(!ans.empty()){
cout<<ans.front()<<endl;
ans.pop();
}
}
/*
3
))))(((
)))
((((
*/
詳細信息
Test #1:
score: 100
Accepted
time: 97ms
memory: 4136kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
1 2 5 7 8 9 10 11 12 13 14 16 19 23 27 28 29 30 32 34 35 37 38 42 43 44 54 55 58 59 61 65 69 70 72 76 77 79 80 87 91 92 93 94 95 96 97 99 103 112 116 117 118 120 122 125 126 127 128 129 130 131 133 135 136 143 146 147 148 149 150 151 154 161 162 163 164 165 166 169 172 175 176 177 178 179 181 182 18...
result:
ok good plan
Test #2:
score: 0
Accepted
time: 9ms
memory: 3460kb
input:
1000 ( ))(())) ((((())())))((())(()))( )( ) ))) ))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()()) )((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))( )))((( ( )))()()()))) ( (((())(((...
output:
1 3 10 12 13 14 17 18 20 22 30 31 33 35 36 39 45 54 58 60 62 64 65 66 75 77 80 83 84 85 88 89 90 92 97 98 101 104 106 110 112 115 122 123 125 126 127 128 131 134 135 136 143 147 162 164 166 168 171 177 178 179 181 182 188 189 190 197 198 206 208 209 212 213 214 215 216 217 221 223 228 229 239 242 24...
result:
ok good plan
Test #3:
score: 0
Accepted
time: 2ms
memory: 3176kb
input:
2 () ()
output:
1 2
result:
ok good plan
Test #4:
score: 0
Accepted
time: 2ms
memory: 3300kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: -100
Wrong Answer
time: 2ms
memory: 3336kb
input:
2 )( ()
output:
2 1
result:
wrong answer wrong plan (expected impossible)