QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#69229#5108. Prehistoric ProgramsrivalqWA 6ms5176kbC++142.2kb2022-12-25 17:37:532022-12-25 17:37:55

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-25 17:37:55]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:5176kb
  • [2022-12-25 17:37:53]
  • 提交

answer

// Jai Shree Ram  
  
#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC



template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}


int solve(){
 		int n; cin >> n;
 		vector<pair<int,pii>> vec;
 		for(int i = 0; i < n; i++){
 			string s; cin >> s;
 			int bal = 0, mn = 0;
 			for(auto j: s){
 				if(j == '(') bal++;
 				else bal--;
 				mins(mn,bal);
 			}
 			vec.push_back({i,{bal,mn}});
 		}
 		sort(all(vec),[&](auto &a, auto &b){
 			if(a.y.x > 0 and b.y.x <= 0) return true;
 			if(a.y.x <= 0 and b.y.x > 0) return false;
 			if(a.y.x > 0 and b.y.x > 0) return a.y.y > b.y.y;
 			return a.y.y < b.y.y;
 		});
 		int sum = 0;
 		vector<int> ans;
 		for(auto [i,p]: vec){
 			auto [bal,mn] = p;
 			if(sum + mn < 0){
 				cout << "impossible" << endl;
 				return 0;
 			} 
 			ans.push_back(i + 1);
 			sum += bal;
 		}
 		if(sum != 0){
 			cout << "impossible" << endl;
 			return 0;
 		}
 		for(auto i: ans) cout << i << endl;
 return 0;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #ifdef SIEVE
    sieve();
    #endif
    #ifdef NCR
    init();
    #endif
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 5176kb

input:

50000
(
(
))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()(
)
(
)
(((
(
(
(
(
(
()
(
)
(
)((())()((
)))))(
(
)
))
)()
(
)
)
)()(
(
(
()
(
)
(
)()((((())()))())(
(
(
)(
(
(
(()())())
)
)
(
(
(
)((())))((())))))))))((((()()))()))))))))((()())()))
)
)()
)
)
)
)
)
())(())))))()(()((()(())...

output:

26315
26345
26341
26339
26336
26334
26333
26329
26328
26327
26321
26320
26318
26317
26316
26347
26313
26311
26308
26307
26305
26302
26297
26295
26294
26292
26290
26289
26286
26384
26414
26413
26412
26409
26406
26402
26401
26399
26398
26396
26395
26394
26393
26285
26383
26382
26380
26376
26370
26366
...

result:

ok good plan

Test #2:

score: 0
Accepted
time: 3ms
memory: 3508kb

input:

1000
(
))(()))
((((())())))((())(()))(
)(
)
)))
))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()())
)((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))(
)))(((
(
)))()()())))
(
(((())(((...

output:

252
267
573
265
799
859
258
257
929
575
253
268
640
576
933
247
707
245
243
242
934
239
287
915
803
301
863
919
296
481
291
290
570
798
286
801
282
925
280
554
553
271
819
945
820
619
198
943
584
793
854
190
189
188
719
585
725
182
181
947
179
178
177
948
638
715
935
577
496
498
711
857
229
228
502
...

result:

ok good plan

Test #3:

score: 0
Accepted
time: 2ms
memory: 3296kb

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

score: 0
Accepted
time: 2ms
memory: 3456kb

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

score: 0
Accepted
time: 2ms
memory: 3300kb

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

score: 0
Accepted
time: 2ms
memory: 3364kb

input:

3
()
(
)

output:

2
3
1

result:

ok good plan

Test #7:

score: 0
Accepted
time: 2ms
memory: 3336kb

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

score: 0
Accepted
time: 2ms
memory: 3352kb

input:

5
))(
(()
)(
(
)

output:

2
4
1
3
5

result:

ok good plan

Test #9:

score: 0
Accepted
time: 2ms
memory: 3344kb

input:

3
((
))())
(

output:

1
3
2

result:

ok good plan

Test #10:

score: 0
Accepted
time: 2ms
memory: 3284kb

input:

6
)
()
()()()
((
)
)

output:

impossible

result:

ok impossible

Test #11:

score: 0
Accepted
time: 2ms
memory: 3308kb

input:

500
(
)
)
(
)(
(
(
)
))(
(
(
(
(
)
)
(
(
)
(
(
)
(
()(()
(
)())
(
(
)
(
)()((
(
)
(
)
)
(
(
(
)
(
(
)
)
)(
(
(
)
)
(
)
(
(
(
)
(
(
())))
(
(
(
)
(
)
)
(
(
)
)
(
(
(
(
(
()
(
(
(
(
(
((
)
(
(
)
(
(
(
)
())
(
(
(
)
(
(
(
)
)
(
)
)
(
)
(
(
(
(
)
(
)
)
)
)
(
)
)))()(
(
)
)
(
)
)(
)
(
)
)
))
(
(
(
(
(
(
...

output:

415
209
208
207
412
205
413
203
414
210
416
199
198
196
194
192
191
420
405
395
232
398
228
227
226
399
404
186
219
406
409
214
410
411
211
153
437
160
159
158
157
156
439
440
436
152
442
149
443
445
143
141
427
184
424
182
180
426
178
177
176
234
428
171
429
431
166
434
435
362
318
315
356
357
311
...

result:

ok good plan

Test #12:

score: -100
Wrong Answer
time: 2ms
memory: 3288kb

input:

50
)
)
((((()())())))(())(())
()(((()))
(((()))(()
()(((
))
)
)()))(()(()())(((((()
(
)
)
)((
)()((
())()))
(())))()
(((
))))(()
()(())(()))())()
)
)
(
(
(
(
((())()())())))(((())
()(
(()(())()((()
()(((()())))())()(
)
)((()
(
)
((
)
()(
(
(
)
)))((())
)
()))()(((()(()
((
((()))(())(()())(()())())()...

output:

impossible

result:

wrong answer you didn't find a solution but jury did