QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107703 | #5384. Floppy Music | PetroTarnavskyi# | AC ✓ | 13ms | 3460kb | C++17 | 946b | 2023-05-22 16:01:07 | 2023-05-22 16:01:10 |
Judging History
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<char> dp(t + 1, 1);
while (n--) {
int l, r;
cin >> l >> r;
int len = r - l;
vector<char> 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: 3432kb
input:
1 6 2 0 4 6 12
output:
possible
result:
ok single line: 'possible'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3348kb
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: 3328kb
input:
1 10000 2 0 10000 990000 1000000
output:
possible
result:
ok single line: 'possible'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3376kb
input:
1 10000 2 1 10002 990000 1000000
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3344kb
input:
1 1 2 1 2 3 4
output:
possible
result:
ok single line: 'possible'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3436kb
input:
1 1 2 1 2 3 5
output:
impossible
result:
ok single line: 'impossible'
Test #7:
score: 0
Accepted
time: 13ms
memory: 3444kb
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: 3ms
memory: 3392kb
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: 1ms
memory: 3448kb
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: 2ms
memory: 3376kb
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: 2ms
memory: 3384kb
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: 3380kb
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: 3368kb
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: 2ms
memory: 3432kb
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: 4ms
memory: 3400kb
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: 0ms
memory: 3448kb
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: 4ms
memory: 3372kb
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: 4ms
memory: 3384kb
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: 2ms
memory: 3368kb
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: 3ms
memory: 3444kb
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: 2ms
memory: 3452kb
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: 3ms
memory: 3448kb
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: 3ms
memory: 3452kb
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: 0ms
memory: 3356kb
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: 3ms
memory: 3376kb
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: 2ms
memory: 3372kb
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: 4ms
memory: 3460kb
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'