QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#640564#6260. Historic Exhibitiondohoon#AC ✓2ms4388kbC++171.1kb2024-10-14 14:20:052024-10-14 14:20:06

Judging History

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

  • [2024-10-14 14:20:06]
  • 评测
  • 测评结果：AC
  • 用时：2ms
  • 内存：4388kb
查看
  • [2024-10-14 14:20:05]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,a,b) for (ll i = (a); i <= (b); ++i)
#define all(x) begin(x),end(x)
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;

const ll N = 10003, M = N;
ll n, m;
vi a[N], b[N];
ll c[M], ans[M];

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    rep(i,1,n) {
        ll x, y;
        cin >> x >> y;
        if (x>y) swap(x,y);
        if (x==y) b[x].pb(i);
        else a[x].pb(i);
    }
    
    rep(i,1,m) {
        cin >> c[i];
    }
    
    vi idxs(m); iota(all(idxs),1), sort(all(idxs), [](ll x, ll y){ return c[x] < c[y]; });
    
    for (auto i : idxs) {
        if (!empty(b[c[i]])) {
            ans[i] = b[c[i]].back();
            b[c[i]].pop_back();
        } else if (!empty(a[c[i]-1])) {
            ans[i] = a[c[i]-1].back();
            a[c[i]-1].pop_back();
        } else if (!empty(a[c[i]])) {
            ans[i] = a[c[i]].back();
            a[c[i]].pop_back();
        }
        else cout << "impossible", exit(0);
    }
    
    rep(i,1,m) {
        cout << ans[i] << '\n';
    }
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3976kb

input:

4 3
1 2
4 5
2 3
2 2
1 2 3

output:

1
4
3

result:

ok correct

Test #2:

score: 0
Accepted
time: 1ms
memory: 3912kb

input:

2 2
1 1
2 3
1 1

output:

impossible

result:

ok impossible

Test #3:

score: 0
Accepted
time: 1ms
memory: 4028kb

input:

2 3
9 8
4 5
4 9 5

output:

impossible

result:

ok impossible

Test #4:

score: 0
Accepted
time: 0ms
memory: 4044kb

input:

1000 1000
141 140
239 240
380 380
114 115
345 345
60 60
341 340
224 223
400 399
125 124
163 162
53 53
62 62
326 326
36 36
91 92
187 186
48 49
123 123
232 233
275 274
374 373
321 322
251 250
347 348
221 222
64 65
143 144
65 65
135 136
209 208
336 336
118 117
189 190
87 86
58 58
66 67
185 185
289 288
...

output:

854
944
166
3
868
201
4
432
131
270
929
931
710
636
533
963
642
323
412
431
317
745
445
836
662
164
393
730
409
420
922
295
448
628
154
387
145
923
326
454
918
120
961
333
129
472
787
646
331
864
426
198
155
30
789
554
272
21
577
491
283
537
832
152
859
17
674
110
910
106
41
266
381
77
536
830
414
1...

result:

ok correct

Test #5:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

100 100
9 9
3 3
9 9
5 4
8 7
19 20
8 8
10 11
19 18
18 18
8 9
20 20
15 14
8 9
16 15
8 7
8 9
7 8
7 8
2 3
5 6
12 13
8 7
14 13
13 13
8 9
3 2
16 15
17 18
15 14
18 19
6 6
14 14
4 3
17 18
16 16
4 3
9 10
3 2
8 8
12 11
4 5
8 8
5 4
5 6
6 5
14 13
9 10
1 2
12 12
19 18
19 18
12 13
11 12
1 1
9 8
8 8
4 3
1 2
3 4
7 ...

output:

58
55
11
7
56
46
60
10
65
31
30
49
83
72
19
16
94
64
87
62
23
66
24
74
79
88
3
100
21
33
92
48
4
61
97
42
27
47
44
82
50
84
95
80
13
99
37
25
91
52
90
6
73
9
71
86
59
5
38
75
43
34
22
26
28
98
63
41
54
77
1
2
12
32
29
40
45
76
78
85
35
57
81
39
18
70
8
68
17
20
69
51
67
96
36
53
15
93
14
89

result:

ok correct

Test #6:

score: 0
Accepted
time: 1ms
memory: 4016kb

input:

100 60
11 11
43 44
15 16
27 27
18 18
8 8
2 1
58 57
23 22
10 11
14 15
9 8
37 38
57 56
32 33
48 49
23 22
13 12
6 5
28 29
4 4
4 3
6 7
14 15
6 7
42 42
5 5
2 2
48 48
2 1
18 17
49 48
15 16
8 7
38 38
35 34
33 32
38 39
36 35
41 40
18 19
7 7
45 44
53 52
11 11
26 25
15 14
35 36
5 4
7 8
56 55
19 18
52 52
35 35...

output:

40
6
7
32
5
81
24
79
70
42
72
29
91
76
58
13
65
22
89
19
57
75
37
71
28
48
69
84
26
43
54
4
47
55
35
98
95
56
30
63
97
45
59
83
100
31
73
61
16
17
62
90
46
67
96
94
9
85
64
53

result:

ok correct

Test #7:

score: 0
Accepted
time: 0ms
memory: 3976kb

input:

10 7
3 4
1 1
4 4
4 5
2 3
6 6
3 2
1 2
4 3
3 4
2 1 5 4 4 3 2

output:

8
2
4
3
10
5
7

result:

ok correct

Test #8:

score: 0
Accepted
time: 0ms
memory: 4140kb

input:

5 3
1 1
3 4
4 3
1 1
1 1
1 1 3

output:

5
4
3

result:

ok correct

Test #9:

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

input:

10000 10000
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
...

output:

6009
9338
9337
9336
9335
9334
9333
9332
9331
9330
9339
9328
9327
9326
9325
9324
9323
9322
9321
9349
9358
9357
9356
9355
9354
9353
9352
9351
9350
9359
9348
9347
9346
9345
9344
9343
9342
9341
9340
9329
9299
9298
9297
9296
9295
9294
9293
9292
9291
9300
9289
9288
9287
9286
9285
9284
9283
9282
9310
9319
...

result:

ok correct

Test #10:

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

input:

10000 10000
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
10 11
...

output:

impossible

result:

ok impossible

Test #11:

score: 0
Accepted
time: 1ms
memory: 4144kb

input:

4 4
1 1
2 2
3 3
1 1
1 2 3 5

output:

impossible

result:

ok impossible

Test #12:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

4 4
1 1
2 2
3 3
1 1
1 2 3 1

output:

4
2
3
1

result:

ok correct

Test #13:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

7 8
2 1
3 2
2 3
5 4
7 6
7 6
8 7
1 2 3 4 5 6 7 8

output:

impossible

result:

ok impossible

Test #14:

score: 0
Accepted
time: 0ms
memory: 4008kb

input:

0 0

output:

result:

ok correct

Test #15:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

1 0
1 1

output:

result:

ok correct

Test #16:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

0 1
1

output:

impossible

result:

ok impossible

Test #17:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

2 0
1 2
2 1

output:

result:

ok correct

Test #18:

score: 0
Accepted
time: 0ms
memory: 4140kb

input:

1 1
2 2
1

output:

impossible

result:

ok impossible

Test #19:

score: 0
Accepted
time: 0ms
memory: 4128kb

input:

12 10
1 2
1 2
2 3
2 3
2 3
2 3
3 3
3 3
3 4
4 5
8 9
8 9
1 1 3 3 3 3 3 3 3 4

output:

2
1
8
7
6
5
4
3
9
10

result:

ok correct

Test #20:

score: 0
Accepted
time: 1ms
memory: 3960kb

input:

4 3
2 1
1 2
1 2
3 2
3 1 2

output:

4
3
2

result:

ok correct

Test #21:

score: 0
Accepted
time: 0ms
memory: 4008kb

input:

3 2
1 1
1 1
1 1
1 1

output:

3
2

result:

ok correct

Test #22:

score: 0
Accepted
time: 0ms
memory: 3972kb

input:

8 8
2 1
3 2
2 3
5 4
5 4
7 6
7 6
8 7
1 2 3 4 5 6 7 8

output:

1
3
2
5
4
7
6
8

result:

ok correct

Test #23:

score: 0
Accepted
time: 0ms
memory: 3976kb

input:

10 5
1824 1825
411 410
4507 4508
4012 4013
3657 3658
3813 3812
9196 9195
3612 3612
107 106
5575 5575
1825 410 4507 4013 3658

output:

1
2
3
4
5

result:

ok correct

Test #24:

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

input:

7907 7305
1614 1614
1911 1912
7213 7213
5742 5742
1445 1446
913 914
5419 5419
8198 8197
4726 4726
1495 1496
908 909
9658 9658
6650 6649
8026 8025
7172 7172
7549 7550
5784 5785
9924 9925
3150 3149
204 204
6536 6537
2009 2008
5111 5112
9724 9723
4407 4407
9448 9448
504 504
2035 2036
808 808
6533 6534
...

output:

impossible

result:

ok impossible

Test #25:

score: 0
Accepted
time: 1ms
memory: 4096kb

input:

5849 2078
1 2
9 10
5 4
4 3
6 6
2 2
10 9
7 6
1 2
7 7
6 7
3 3
5 6
3 2
6 5
4 4
10 9
4 4
5 6
9 9
8 9
8 8
8 9
1 1
5 6
5 6
6 7
3 3
3 3
7 8
1 1
1 1
10 9
9 8
10 10
2 2
5 5
3 4
5 5
10 10
6 5
8 9
8 9
5 4
10 9
5 4
7 8
4 5
3 3
1 1
4 3
10 10
1 2
2 1
8 9
10 10
8 9
8 8
6 5
5 5
5 6
4 4
8 8
3 3
3 3
9 10
9 10
8 8
3 4...

output:

5037
914
898
1835
1845
2810
781
2788
5
5034
1871
660
5506
1043
284
2648
5387
4849
2578
3618
2987
867
1482
2997
1053
5549
845
3150
2419
2415
2722
5043
5051
5640
1569
1094
5754
5165
2137
3841
3458
4946
3525
5450
3274
2328
2235
4551
4261
3234
4685
4300
3230
633
2320
4481
3362
4430
2664
4308
2728
1546
2...

result:

ok correct

Test #26:

score: 0
Accepted
time: 1ms
memory: 4164kb

input:

6860 65
4385 4384
6177 6177
2840 2841
9943 9943
7434 7434
3062 3062
6494 6495
2996 2997
398 398
3079 3078
9199 9198
6932 6931
5376 5376
1247 1247
6853 6854
8779 8780
3534 3533
2548 2547
5477 5477
7404 7404
1603 1603
8023 8023
1990 1991
1776 1776
9769 9768
8250 8250
6182 6181
6496 6497
1046 1045
3839...

output:

impossible

result:

ok impossible

Test #27:

score: 0
Accepted
time: 1ms
memory: 3988kb

input:

2307 1314
7 6
7 7
3 4
6 5
1 1
6 7
4 5
5 4
4 3
8 8
8 7
9 10
9 8
2 1
7 6
9 9
2 3
7 6
6 6
6 6
7 7
6 5
8 9
3 3
7 7
10 10
4 3
9 9
2 3
9 10
3 3
5 4
6 7
4 4
1 1
4 4
2 1
1 2
7 8
9 10
5 5
9 9
8 7
1 2
8 8
1 2
4 4
9 8
3 2
9 8
10 10
4 3
5 5
9 8
6 6
6 7
7 7
3 4
3 2
7 8
10 10
3 4
8 8
4 3
8 7
1 2
2 3
10 9
6 7
1 2
...

output:

790
128
2043
1928
1829
1440
380
2242
1587
1480
120
486
256
1685
864
2001
1157
217
872
958
959
416
646
92
79
81
2154
1687
327
1676
24
2295
1946
2112
208
1949
2297
1998
2058
1669
1063
1966
2290
1751
1109
1432
1717
1971
1730
516
2085
1286
2005
2289
1980
183
363
1748
1939
1965
283
2269
707
744
777
1765
...

result:

ok correct

Test #28:

score: 0
Accepted
time: 1ms
memory: 4388kb

input:

7314 4728
6 7
10 9
5 6
6 7
10 10
1 2
8 9
7 7
5 6
1 2
3 2
2 2
3 3
6 6
6 5
7 6
5 5
7 6
9 10
4 5
9 8
9 9
10 9
7 7
9 10
1 2
8 7
3 4
1 2
5 5
3 3
8 8
6 5
3 3
1 2
1 1
2 3
9 10
7 8
2 1
10 9
6 5
9 8
7 8
8 8
7 7
1 2
3 2
7 6
9 10
4 3
5 6
9 10
8 7
1 2
10 9
10 9
3 4
1 2
5 6
4 5
8 7
8 7
3 4
3 4
8 7
3 2
1 1
8 7
4 ...

output:

4274
6894
4685
6677
7053
5164
4642
4862
4989
6504
3586
4375
4698
4296
4313
4503
4371
4820
4373
5224
6643
4319
3283
3947
5163
6788
6433
6838
4891
6841
4533
6984
6124
4167
5371
347
3323
6523
5010
4299
6746
3327
6191
3583
5357
7152
5064
3689
6036
5306
5294
6787
3680
6025
4116
3938
4201
6691
4260
5186
6...

result:

ok correct

Test #29:

score: 0
Accepted
time: 1ms
memory: 4120kb

input:

9031 3313
1 1
8 7
2 2
1 1
1 1
7 7
10 10
4 5
3 3
4 5
2 1
6 6
2 1
7 7
5 6
6 6
2 2
5 5
5 5
5 4
7 7
8 8
2 3
7 7
9 9
1 2
4 3
1 2
7 6
5 4
2 2
7 7
2 3
8 8
5 4
4 5
5 6
8 9
6 6
4 3
2 1
7 7
2 1
4 4
1 1
2 3
4 4
5 6
3 2
1 2
6 7
3 2
8 9
9 8
8 8
3 4
7 7
8 8
3 2
5 5
2 3
1 2
4 4
6 7
9 9
4 3
4 4
6 7
2 2
2 1
4 5
10 1...

output:

1881
5535
5478
7072
2598
1920
7686
6276
6368
2180
205
2204
2260
3060
2371
2660
3939
4255
5452
3693
7706
7710
2125
2128
4785
4869
7586
953
5283
2588
5259
3792
4945
12
4469
3678
5787
4936
8993
8991
4353
8001
8028
7450
8939
5030
2351
2364
4088
4856
7778
6179
4838
3659
4229
4201
3556
4368
4913
6727
3035...

result:

ok correct

Test #30:

score: 0
Accepted
time: 1ms
memory: 4048kb

input:

4282 507
5 5
7 6
4 3
7 8
1 1
2 1
10 10
10 10
7 6
3 2
6 7
7 8
1 1
4 4
6 5
10 10
5 4
3 4
9 8
3 3
6 5
1 1
6 7
2 2
10 10
5 5
6 7
4 5
9 9
1 2
8 7
3 3
6 7
3 2
1 1
5 4
7 8
4 4
6 5
6 6
7 7
10 10
1 1
7 8
8 9
3 3
3 4
6 7
3 3
10 9
6 6
2 2
2 2
2 1
10 10
2 2
3 4
10 9
10 9
4 5
3 4
4 5
2 3
7 8
2 2
2 1
5 4
2 1
3 2
...

output:

3491
4177
3044
3099
2722
3693
2660
4231
3287
3168
3840
3165
3819
3122
4126
3363
3581
3486
3777
4039
3587
3032
2856
4038
3453
3438
4064
3474
3972
3077
3367
3101
3909
4179
3041
3449
3832
3399
3695
3409
3431
3639
2933
3441
3314
3112
3243
3729
3460
4081
3665
3466
3355
3351
3873
3434
3311
4158
3533
3752
...

result:

ok correct

Test #31:

score: 0
Accepted
time: 1ms
memory: 4256kb

input:

5976 8723
5 6
10 10
7 7
5 6
9 8
7 8
10 10
9 10
3 4
3 4
7 6
2 2
7 8
9 8
4 5
10 9
10 10
9 9
7 6
4 5
4 3
9 9
9 9
7 8
3 2
8 9
4 5
7 8
7 8
6 5
5 4
2 2
10 10
5 6
5 6
3 4
1 1
7 8
3 2
6 5
8 7
5 5
7 8
3 2
2 3
1 2
2 3
6 7
9 10
2 3
6 6
8 8
2 1
1 2
3 4
8 7
10 9
1 1
5 5
2 2
3 3
4 5
3 4
9 8
1 2
8 8
5 6
3 3
5 4
8 ...

output:

impossible

result:

ok impossible

Test #32:

score: 0
Accepted
time: 1ms
memory: 4248kb

input:

7389 5821
1 2
6 5
10 9
9 10
10 9
3 3
8 8
1 1
3 4
8 7
1 2
9 8
4 4
10 9
10 9
9 10
5 4
10 10
6 7
9 10
8 9
2 3
7 6
7 7
10 9
3 2
10 10
7 6
6 6
2 2
6 6
3 2
9 8
4 3
3 4
4 5
10 10
8 8
1 2
2 2
4 5
7 8
1 1
6 7
9 9
9 9
10 9
3 2
2 1
5 6
10 10
10 10
6 7
6 6
6 5
1 1
3 4
1 1
8 9
1 1
2 1
3 2
7 7
5 5
7 7
6 7
7 6
4 4...

output:

7324
3981
5581
4753
1827
5739
6410
2436
5209
2750
2694
2609
3412
4835
6889
2448
2859
2157
4145
5556
2137
6406
7219
1742
5876
859
7113
1707
2508
4441
4572
3621
2533
2782
3943
3069
3689
3920
4218
4224
3235
3837
3371
2537
4891
5907
4051
5956
4044
5068
6821
3272
2491
5603
1933
5690
6073
6849
3458
4464
5...

result:

ok correct

Test #33:

score: 0
Accepted
time: 1ms
memory: 4208kb

input:

3326 8220
3 2
8 9
1 2
4 4
1 2
4 5
6 5
3 4
3 4
10 10
8 9
8 7
3 4
3 3
6 7
1 2
3 3
8 9
1 2
1 2
10 9
7 7
8 7
4 3
1 1
2 3
6 7
10 9
7 7
7 7
10 9
1 1
2 2
4 5
8 7
8 7
8 9
10 9
2 1
6 6
5 6
8 7
2 1
10 9
3 4
7 7
4 4
4 3
10 9
1 2
2 1
10 9
2 1
6 5
6 6
2 1
2 2
5 5
6 7
1 1
10 10
9 8
5 6
7 7
9 9
5 5
2 2
4 5
4 5
5 6...

output:

impossible

result:

ok impossible

Test #34:

score: 0
Accepted
time: 0ms
memory: 4012kb

input:

4 3
2 3
3 2
3 2
1 2
1 3 2

output:

4
2
3

result:

ok correct

Test #35:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

7 7
2 1
2 1
2 3
4 3
6 5
7 6
7 6
1 2 3 4 5 6 7

output:

2
1
3
4
5
7
6

result:

ok correct

Test #36:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

6 7
3 2
4 3
4 5
5 4
6 5
7 6
1 2 3 4 5 6 7

output:

impossible

result:

ok impossible

Test #37:

score: 0
Accepted
time: 1ms
memory: 4188kb

input:

3 3
3 4
5 6
8 9
6 7 8

output:

impossible

result:

ok impossible

Test #38:

score: 0
Accepted
time: 0ms
memory: 4000kb

input:

1 1
1 2
3

output:

impossible

result:

ok impossible

Test #39:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

3 3
100 101
101 101
101 102
101 101 101

output:

2
1
3

result:

ok correct
English 繁體中文 简体中文

Server Time: 2024-12-02 15:04:52 | OpenSource Project