QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#66063 | #5108. Prehistoric Programs | rumen_m# | WA | 136ms | 6204kb | C++14 | 3.1kb | 2022-12-06 03:29:19 | 2022-12-06 03:29:21 |
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,c;
bool got[MAXN];
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,i});
c.push_back({-seq[i].ends,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());
sort(c.begin(),c.end());
int uk1 = 0,uk2 = 0;
// cout<<currD<<endl;
while(uk1<b.size())
{
while(uk1<b.size() && got[b[uk1].second])uk1++;
while(uk2<c.size() && got[c[uk2].second]) uk2++;
if(uk1==b.size())break;
if(b[uk1].second!=c[uk2].second && (currD + seq[c[uk2].second].ends + seq[b[uk1].second].nms) >= 0)
{
// cout<<"Ok"<<endl;
currD += seq[c[uk2].second].ends;
ans.push(c[uk2].second);
got[c[uk2].second] = 1;
}else
{
// cout<<"OKK"<<endl;
if(currD+seq[b[uk1].second].nms < 0){cout<<(seq[b[uk1].second].nms+currD)<<"impossible\n";return 0;}
currD += seq[b[uk1].second].ends;
got[b[uk1].second]=1;
ans.push(b[uk1].second);
}
}*/
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: 136ms
memory: 6204kb
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: 1ms
memory: 3308kb
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: 0ms
memory: 3256kb
input:
2 () ()
output:
1 2
result:
ok good plan
Test #4:
score: 0
Accepted
time: 3ms
memory: 5192kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 5376kb
input:
2 )( ()
output:
2 1
result:
wrong answer wrong plan (expected impossible)