QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107702#5384. Floppy MusicPetroTarnavskyi#AC ✓7ms3524kbC++17944b2023-05-22 16:00:412023-05-22 16:00:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-22 16:00:43]
  • 评测
  • 测评结果:AC
  • 用时:7ms
  • 内存:3524kb
  • [2023-05-22 16:00:41]
  • 提交

answer

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

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int f;
	cin >> f;
	bool ans = true;
	while (f--) {
		int t, n;
		cin >> t >> n;
		vector<int> dp(t + 1, 1);
		while (n--) {
			int l, r;
			cin >> l >> r;
			int len = r - l;
			vector<int> ndp(t + 1);
			FOR(j, 0, t + 1) {
				if (j + len <= t) {
					ndp[j + len] |= dp[j];
				}
				if (j - len >= 0) {
					ndp[j - len] |= dp[j];
				}
			}
			dp = ndp;
		}
		ans &= accumulate(ALL(dp), 0) != 0;
	}
	if (!ans) {
		cout << "im";
	}
	cout << "possible\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3436kb

input:

1
6 2
0 4
6 12

output:

possible

result:

ok single line: 'possible'

Test #2:

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

input:

1
6 3
0 5
6 8
9 14

output:

impossible

result:

ok single line: 'impossible'

Test #3:

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

input:

1
10000 2
0 10000
990000 1000000

output:

possible

result:

ok single line: 'possible'

Test #4:

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

input:

1
10000 2
1 10002
990000 1000000

output:

impossible

result:

ok single line: 'impossible'

Test #5:

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

input:

1
1 2
1 2
3 4

output:

possible

result:

ok single line: 'possible'

Test #6:

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

input:

1
1 2
1 2
3 5

output:

impossible

result:

ok single line: 'impossible'

Test #7:

score: 0
Accepted
time: 7ms
memory: 3412kb

input:

10
10000 100
22 78
86 112
165 200
283 368
441 506
542 565
576 597
683 776
875 958
1020 1111
1174 1242
1267 1352
1423 1472
1491 1585
1609 1704
1713 1779
1797 1849
1870 1899
1921 2005
2084 2103
2123 2157
2230 2303
2332 2400
2412 2463
2470 2484
2558 2591
2671 2753
2779 2851
2871 2926
2961 2991
3086 318...

output:

possible

result:

ok single line: 'possible'

Test #8:

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

input:

7
7982 63
5419 8609
12279 15901
21280 22127
25534 28854
32746 38025
43555 48911
53164 55072
58283 63842
66546 71475
76018 78894
83864 88900
93309 97796
102097 103772
104561 107998
111601 114622
117735 122757
124691 128199
131789 136151
137937 139849
141519 143338
143453 147152
147686 152946
154136 1...

output:

possible

result:

ok single line: 'possible'

Test #9:

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

input:

6
8421 8
1140 1775
6665 9136
13822 19656
24852 29906
34476 37676
41940 42519
47990 51976
57202 60998
676 84
280 322
512 932
1233 1240
1262 1334
1464 1854
2139 2345
2423 2436
2601 2789
2808 2862
2937 3228
3307 3600
4067 4349
4817 5184
5310 5363
5769 5941
6082 6168
6492 6767
6931 7042
7205 7676
7744 7...

output:

impossible

result:

ok single line: 'impossible'

Test #10:

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

input:

4
4804 27
1017 4190
5603 6046
8813 9612
12153 13571
13985 16859
19908 21435
24164 26533
29780 31466
32435 33880
35432 37312
38612 40765
44035 45309
46283 47995
50477 51317
53739 55148
57536 58634
60698 62196
65458 66969
67702 69845
70290 73091
73269 75616
77921 78274
80111 82496
84087 86118
89215 91...

output:

possible

result:

ok single line: 'possible'

Test #11:

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

input:

8
1756 53
964 1347
2177 2508
3364 4403
5412 5721
6332 6921
8073 8361
8476 8840
10037 10205
10734 11514
12671 13330
13573 14640
15412 16260
16280 17036
17118 17759
18957 19799
19943 20541
21180 21978
23150 23549
23753 24761
24816 25070
25449 26514
26660 27653
28242 29444
29636 30319
31153 31459
32054...

output:

possible

result:

ok single line: 'possible'

Test #12:

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

input:

1
1038 95
159 746
1185 1482
1926 2338
3017 3593
3956 4591
4692 5255
5380 5513
5793 5935
6558 7108
7657 7715
7763 8124
8727 9216
9738 10056
10347 10930
11473 12141
12552 12586
12610 13312
13531 13723
14030 14313
14315 14741
14817 14839
15561 16171
16510 16813
16818 17478
17545 18261
18841 19155
19650...

output:

possible

result:

ok single line: 'possible'

Test #13:

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

input:

6
3680 15
2361 2891
3534 5237
7438 9488
11181 12000
13727 15608
16501 18248
18588 20544
20745 22933
23366 25877
26700 29119
30344 31260
32537 32973
33015 33486
34980 36493
37306 37917
7931 93
5538 6633
8157 8704
9637 12213
16332 17582
18864 22300
26423 28058
29056 31791
32277 36729
40018 41755
44665...

output:

possible

result:

ok single line: 'possible'

Test #14:

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

input:

1
4621 44
2560 2968
3218 6330
7435 10144
11667 11696
13057 14958
16481 17299
18216 19408
21865 23412
24349 27251
27886 30957
31192 34267
35760 37300
40031 40815
42735 44221
45244 46168
48160 48351
50770 52542
55713 57137
60205 60659
62146 63536
64445 65916
68832 71881
74052 74286
76422 77809
79472 8...

output:

possible

result:

ok single line: 'possible'

Test #15:

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

input:

10
1301 65
296 681
872 1755
2637 3484
4384 4735
5212 6001
6616 7201
7296 8019
8514 9166
9207 9232
9526 10391
11062 11384
11409 11758
12370 13079
13431 13869
14100 14270
14347 14801
14946 15402
16091 16946
17423 18317
18748 19041
19580 20191
21045 21353
22181 22933
23050 23453
23961 24050
24287 24757...

output:

possible

result:

ok single line: 'possible'

Test #16:

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

input:

2
3501 11
1124 2656
4132 6134
6362 7087
8609 8703
9169 11337
12783 13167
13936 15302
15378 15515
16036 17638
18101 19073
20828 20902
2042 97
822 980
1332 2221
2810 3019
4341 4478
4504 5790
6982 7730
8563 8986
10017 10240
10485 11805
11989 12570
12636 13799
14279 14527
15185 16130
17085 17536
17865 1...

output:

possible

result:

ok single line: 'possible'

Test #17:

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

input:

10
4219 33
1151 1285
4237 6962
8132 9867
12019 14023
14611 17190
17418 19917
20462 21782
23672 24114
26964 28089
29406 29702
30139 32168
34606 37425
39806 40169
40424 41451
42888 43791
44486 46159
47152 48056
49919 51228
52173 54681
57447 59686
61692 64171
66161 67438
68588 70738
71114 73834
74218 7...

output:

impossible

result:

ok single line: 'impossible'

Test #18:

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

input:

8
8674 76
3748 7626
10500 15020
20651 26253
29334 35020
40672 44862
50901 53977
59930 62312
66166 70360
71928 72600
77438 78071
78796 83504
83809 85949
90383 90385
92379 94838
98585 103635
103729 108548
110720 115690
118149 124159
128197 128317
129466 134634
137508 140920
143677 148776
151187 153307...

output:

possible

result:

ok single line: 'possible'

Test #19:

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

input:

5
3089 5
384 995
1537 1574
3080 4208
5182 6625
7615 8872
4938 76
1555 3281
5341 8260
8438 11180
13196 13651
14268 17037
19760 22150
24041 27149
28638 28826
31195 32440
33974 36095
38599 41112
42975 45203
48086 50143
52669 55286
55638 58990
61093 62086
63129 64771
65995 66928
68368 69855
73013 74633
...

output:

possible

result:

ok single line: 'possible'

Test #20:

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

input:

3
3167 97
1663 3038
4205 5238
6081 7135
7982 8259
8449 9195
10418 12200
13422 13720
15582 15936
17804 18510
18840 19068
19531 20764
21349 21428
23622 23784
24588 26175
28273 30259
31624 32475
33231 34453
35240 36734
37016 38551
39616 40985
42579 44560
44584 46713
47188 48554
49231 50281
52194 52627
...

output:

impossible

result:

ok single line: 'impossible'

Test #21:

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

input:

10
3181 57
2003 3612
3959 3973
4826 5111
6304 8204
8454 8929
10403 11043
13023 14653
16753 17939
18537 19097
19953 20886
22898 23971
24495 26355
28286 29136
29142 30466
31409 31772
32011 33124
33251 33951
35688 37344
37555 37823
39814 39991
41078 41624
41823 42313
43690 43939
45877 46150
46289 46892...

output:

impossible

result:

ok single line: 'impossible'

Test #22:

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

input:

10
9730 2
2019 6042
9131 11176
2337 17
1421 2349
3823 4529
5995 7198
8678 9399
10919 11164
12760 14189
14590 15058
16459 17928
18718 19970
21269 22199
22222 22551
23187 23503
23723 24654
24937 25560
25697 25807
27413 27679
28213 29320
310 64
31 77
93 232
239 424
443 462
670 828
870 1070
1110 1111
12...

output:

possible

result:

ok single line: 'possible'

Test #23:

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

input:

6
2335 14
1191 1961
3158 3714
4864 6122
6344 7128
7204 8250
9215 10154
11655 11779
12514 12589
12926 14465
15645 17199
18750 19418
20791 20972
22445 23409
24322 25714
429 64
255 348
533 564
710 820
1022 1036
1261 1516
1559 1792
1965 2054
2163 2184
2302 2479
2535 2566
2678 2978
3109 3273
3477 3598
37...

output:

impossible

result:

ok single line: 'impossible'

Test #24:

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

input:

2
2858 48
787 904
1550 1697
3649 3687
3891 4014
5600 6487
7879 9510
10792 12267
12590 13455
14044 15464
16989 17011
18130 19118
19416 19996
21651 22101
23517 24600
26184 26688
27478 28927
29929 30467
30473 31386
32150 33612
34311 36019
37395 38529
38647 40069
41094 42103
43263 43703
43996 44761
4534...

output:

impossible

result:

ok single line: 'impossible'

Test #25:

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

input:

10
1647 86
493 675
1629 2069
2640 2762
3452 4368
4706 4795
5794 6263
6304 7204
8314 8642
8820 9251
9498 10300
10551 10862
11162 12284
12876 12993
14110 14807
15805 15827
16914 17592
18497 19340
20026 20131
20257 20543
21446 22464
23348 24032
24843 25381
25773 25802
26362 26408
27315 27442
27500 2758...

output:

impossible

result:

ok single line: 'impossible'

Test #26:

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

input:

3
8388 42
5389 10901
15542 19307
24979 30486
35968 38374
42974 44522
50132 50653
51728 56582
59586 61574
64041 69179
71484 74067
75377 80189
81782 85514
89150 90804
93568 99178
100179 103939
109035 110380
110500 114541
116337 118508
120489 125746
129832 131185
131653 135691
136012 140344
143689 1452...

output:

possible

result:

ok single line: 'possible'

Test #27:

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

input:

7
9438 70
3800 3825
9256 12866
13303 19482
23939 26862
28225 34398
40816 41609
42288 48471
54201 60500
63969 69245
73243 75777
77644 78884
80154 82761
88220 88540
92428 94552
100588 101545
105057 106065
108639 114805
121322 125896
131326 131551
133041 138239
142765 144850
150216 156221
159134 164584...

output:

impossible

result:

ok single line: 'impossible'