QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#66055 | #5108. Prehistoric Programs | rumen_m# | WA | 174ms | 4268kb | C++14 | 2.2kb | 2022-12-06 03:02:06 | 2022-12-06 03:02:08 |
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;
if(currD < seq[curr].nms){cout<<"impossible\n";return 0;}
currD += seq[curr].ends;
ans.push(curr);
}
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
))))(((
)))
((((
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 174ms
memory: 4268kb
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: 8ms
memory: 3240kb
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: 3240kb
input:
2 () ()
output:
1 2
result:
ok good plan
Test #4:
score: 0
Accepted
time: 1ms
memory: 3332kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: -100
Wrong Answer
time: 2ms
memory: 3228kb
input:
2 )( ()
output:
2 1
result:
wrong answer wrong plan (expected impossible)