| Task: | Jakarta Skyscrapers |
| Sender: | Olli |
| Submission time: | 2019-04-07 15:20:31 +0300 |
| Language: | C++ |
| Status: | READY |
| Result: | 36 |
| group | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 10 |
| #2 | ACCEPTED | 12 |
| #3 | ACCEPTED | 14 |
| #4 | TIME LIMIT EXCEEDED | 0 |
| #5 | TIME LIMIT EXCEEDED | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.04 s | 1, 2, 3, 4, 5 | details |
| #2 | ACCEPTED | 0.04 s | 1, 2, 3, 4, 5 | details |
| #3 | ACCEPTED | 0.04 s | 1, 2, 3, 4, 5 | details |
| #4 | ACCEPTED | 0.04 s | 1, 2, 3, 4, 5 | details |
| #5 | ACCEPTED | 0.05 s | 1, 2, 3, 4, 5 | details |
| #6 | ACCEPTED | 0.04 s | 1, 2, 3, 4, 5 | details |
| #7 | ACCEPTED | 0.05 s | 2, 3, 4, 5 | details |
| #8 | ACCEPTED | 0.04 s | 2, 3, 4, 5 | details |
| #9 | ACCEPTED | 0.06 s | 2, 3, 4, 5 | details |
| #10 | ACCEPTED | 0.07 s | 2, 3, 4, 5 | details |
| #11 | ACCEPTED | 0.05 s | 2, 3, 4, 5 | details |
| #12 | ACCEPTED | 0.10 s | 2, 3, 4, 5 | details |
| #13 | ACCEPTED | 0.07 s | 2, 3, 4, 5 | details |
| #14 | ACCEPTED | 0.07 s | 2, 3, 4, 5 | details |
| #15 | ACCEPTED | 0.09 s | 3, 4, 5 | details |
| #16 | ACCEPTED | 0.08 s | 3, 4, 5 | details |
| #17 | ACCEPTED | 0.12 s | 3, 4, 5 | details |
| #18 | ACCEPTED | 0.10 s | 3, 4, 5 | details |
| #19 | ACCEPTED | 0.15 s | 3, 4, 5 | details |
| #20 | ACCEPTED | 0.11 s | 3, 4, 5 | details |
| #21 | ACCEPTED | 0.09 s | 3, 4, 5 | details |
| #22 | ACCEPTED | 0.10 s | 3, 4, 5 | details |
| #23 | ACCEPTED | 0.13 s | 3, 4, 5 | details |
| #24 | ACCEPTED | 0.14 s | 3, 4, 5 | details |
| #25 | ACCEPTED | 0.07 s | 3, 4, 5 | details |
| #26 | ACCEPTED | 0.06 s | 3, 4, 5 | details |
| #27 | ACCEPTED | 0.11 s | 3, 4, 5 | details |
| #28 | ACCEPTED | 0.06 s | 3, 4, 5 | details |
| #29 | ACCEPTED | 0.06 s | 3, 4, 5 | details |
| #30 | ACCEPTED | 0.06 s | 3, 4, 5 | details |
| #31 | ACCEPTED | 0.06 s | 3, 4, 5 | details |
| #32 | ACCEPTED | 0.07 s | 3, 4, 5 | details |
| #33 | ACCEPTED | 0.07 s | 3, 4, 5 | details |
| #34 | ACCEPTED | 0.30 s | 4, 5 | details |
| #35 | ACCEPTED | 0.37 s | 4, 5 | details |
| #36 | ACCEPTED | 0.33 s | 4, 5 | details |
| #37 | ACCEPTED | 0.43 s | 4, 5 | details |
| #38 | ACCEPTED | 0.44 s | 4, 5 | details |
| #39 | ACCEPTED | 0.43 s | 4, 5 | details |
| #40 | ACCEPTED | 0.48 s | 4, 5 | details |
| #41 | ACCEPTED | 0.23 s | 4, 5 | details |
| #42 | ACCEPTED | 0.22 s | 4, 5 | details |
| #43 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #44 | ACCEPTED | 0.40 s | 4, 5 | details |
| #45 | ACCEPTED | 0.41 s | 4, 5 | details |
| #46 | ACCEPTED | 0.56 s | 5 | details |
| #47 | ACCEPTED | 0.64 s | 5 | details |
| #48 | ACCEPTED | 0.72 s | 5 | details |
| #49 | ACCEPTED | 0.57 s | 5 | details |
| #50 | ACCEPTED | 0.85 s | 5 | details |
| #51 | ACCEPTED | 0.87 s | 5 | details |
| #52 | ACCEPTED | 0.80 s | 5 | details |
| #53 | ACCEPTED | 0.09 s | 5 | details |
| #54 | ACCEPTED | 0.08 s | 5 | details |
| #55 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #56 | ACCEPTED | 0.23 s | 5 | details |
| #57 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #58 | ACCEPTED | 0.25 s | 5 | details |
| #59 | ACCEPTED | 0.28 s | 5 | details |
| #60 | ACCEPTED | 0.32 s | 5 | details |
| #61 | ACCEPTED | 0.44 s | 5 | details |
| #62 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #63 | ACCEPTED | 0.45 s | 5 | details |
| #64 | ACCEPTED | 0.43 s | 5 | details |
| #65 | ACCEPTED | 0.41 s | 5 | details |
| #66 | ACCEPTED | 0.44 s | 5 | details |
| #67 | ACCEPTED | 0.47 s | 5 | details |
Compiler report
input/code.cpp: In function 'int main()':
input/code.cpp:34:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < sky[sk].size(); ++j) {
~~^~~~~~~~~~~~~~~~
input/code.cpp:67:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < mod[jum[a]][rem].size(); ++j) {
~~^~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:86:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k = 0; k < sky[j].size(); ++k) {
~~^~~~~~~~~~~~~~~Code
#include <iostream>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
const int M = 3e4 + 5;
const int C = 1e3;
const ll INF = 1e13;
ll loc[M];
ll jum[M];
bool z[M];
vector<int> mod[C+1][C];
vector<int> sky[M];
ll val[M];
int main() {
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
cin >> loc[i] >> jum[i];
sky[loc[i]].push_back(i);
val[i] = -1;
}
for(int mo = 1; mo <= C; ++mo) {
for(int rem = 0; rem < mo; ++rem) {
for(int sk = rem; sk < n; sk += mo) {
for(int j = 0; j < sky[sk].size(); ++j) {
mod[mo][rem].push_back(sky[sk][j]);
}
}
}
}
/* priority_queue<pair<ll, int> > q;
q.push({0, 1});
*/
set<pair<ll, int> > q;
q.insert({0, 1});
// while(!q.empty()) {
while(q.size() != 0) {
// int a = q.top().second;
// ll d = q.top().first; d = -d;
// q.pop();
auto it = q.begin();
int a = (*it).second;
ll d = (*it).first;
q.erase(it);
if(a == 2) {
cout << d << "\n";
return 0;
}
if(z[a]) continue;
z[a] = true;
if(jum[a] <= C) {
int rem = loc[a]%jum[a];
for(int j = 0; j < mod[jum[a]][rem].size(); ++j) {
int k = mod[jum[a]][rem][j];
if(z[k]) continue;
ll comp = d + abs(loc[k] - loc[a])/jum[a];
if(val[k] != -1) {
if(val[k] > comp) {
q.erase({val[k], k});
} else {
continue;
}
}
// q.push({-(d + abs(loc[k] - loc[a])/jum[a]), k});
q.insert({comp, k});
val[k] = comp;
}
} else {
int rem = loc[a]%jum[a];
for(int j = rem; j < n; j += jum[a]) {
for(int k = 0; k < sky[j].size(); ++k) {
int doge = sky[j][k];
if(z[doge]) continue;
ll comp = d + abs(loc[doge] - loc[a])/jum[a];
if(val[doge] != -1) {
if(val[doge] > comp) {
q.erase({val[doge], doge});
} else {
continue;
}
}
// q.push({-(d + abs(loc[doge] - loc[a])/jum[a]), doge});
q.insert({comp, doge});
val[doge] = comp;
}
}
}
}
cout << -1 << "\n";
}Test details
Test 1
Group: 1, 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 1 2 0 1 0 1 |
| correct output |
|---|
| 0 |
| user output |
|---|
| 0 |
Test 2
Group: 1, 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 6 3 0 4 0 4 1 3 |
| correct output |
|---|
| 0 |
| user output |
|---|
| 0 |
Test 3
Group: 1, 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 7 3 3 9 5 8 0 8 |
| correct output |
|---|
| -1 |
| user output |
|---|
| -1 |
Test 4
Group: 1, 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 10 3 0 1 2 3 3 9 |
| correct output |
|---|
| 2 |
| user output |
|---|
| 2 |
Test 5
Group: 1, 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 10 3 0 2 5 1 8 3 |
| correct output |
|---|
| 5 |
| user output |
|---|
| 5 |
Test 6
Group: 1, 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 10 3 0 1 9 1 1 1 |
| correct output |
|---|
| 9 |
| user output |
|---|
| 9 |
Test 7
Group: 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 37 19 20 1 21 56 1 47 27 7 ... |
| correct output |
|---|
| 1 |
| user output |
|---|
| 1 |
Test 8
Group: 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 59 48 36 5 14 8 5 13 17 24 ... |
| correct output |
|---|
| 9 |
| user output |
|---|
| 9 |
Test 9
Group: 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 100 403 22 25 49 8 56 85 50 32 ... |
| correct output |
|---|
| 3 |
| user output |
|---|
| 3 |
Test 10
Group: 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 100 2000 42 40 54 31 95 26 14 71 ... |
| correct output |
|---|
| 1 |
| user output |
|---|
| 1 |
Test 11
Group: 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 100 2000 0 2 91 1 98 3 5 5 ... |
| correct output |
|---|
| 118 |
| user output |
|---|
| 118 |
Test 12
Group: 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 100 2000 0 1 99 1 98 1 98 1 ... |
| correct output |
|---|
| 99 |
| user output |
|---|
| 99 |
Test 13
Group: 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 100 2000 0 1 59 1 29 59 6 51 ... |
| correct output |
|---|
| 59 |
| user output |
|---|
| 59 |
Test 14
Group: 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 100 2000 0 1 99 1 6 22 8 18 ... |
| correct output |
|---|
| 2 |
| user output |
|---|
| 2 |
Test 15
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 200 1704 152 114 197 195 179 101 44 40 ... |
| correct output |
|---|
| 2 |
| user output |
|---|
| 2 |
Test 16
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 742 723 450 221 144 118 273 219 368 196 ... |
| correct output |
|---|
| -1 |
| user output |
|---|
| -1 |
Test 17
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 1747 1189 405 1135 675 1863 1151 273 826 345 ... |
| correct output |
|---|
| -1 |
| user output |
|---|
| -1 |
Test 18
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 1046 854 1720 652 413 1598 1407 843 1784 ... |
| correct output |
|---|
| 32 |
| user output |
|---|
| 32 |
Test 19
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 2000 0 1 1999 1 1100 1 1402 1 ... |
| correct output |
|---|
| 1999 |
| user output |
|---|
| 1999 |
Test 20
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 657 1595 255 533 391 1570 353 1230 400 100 ... |
| correct output |
|---|
| 32 |
| user output |
|---|
| 32 |
Test 21
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 1596 640 607 511 1446 1150 27 471 918 1084 ... |
| correct output |
|---|
| -1 |
| user output |
|---|
| -1 |
Test 22
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 1210 837 455 275 375 64 203 319 654 1970 ... |
| correct output |
|---|
| -1 |
| user output |
|---|
| -1 |
Test 23
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 1928 1716 1608 1878 688 110 1243 786 1225 599 ... |
| correct output |
|---|
| 12 |
| user output |
|---|
| 12 |
Test 24
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 2000 1998 2 1 1 0 3 1999 1 ... |
| correct output |
|---|
| 498 |
| user output |
|---|
| 498 |
Test 25
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 2000 0 2 1999 1 1998 3 3 5 ... |
| correct output |
|---|
| 2892 |
| user output |
|---|
| 2892 |
Test 26
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 2000 0 2 1607 1 1998 3 3 5 ... |
| correct output |
|---|
| 3340 |
| user output |
|---|
| 3340 |
Test 27
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 2000 461 538 0 1 964 1999 1097 1999 ... |
| correct output |
|---|
| 17769 |
| user output |
|---|
| 17769 |
Test 28
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 746 0 1 1698 1 30 31 16 35 ... |
| correct output |
|---|
| 1698 |
| user output |
|---|
| 1698 |
Test 29
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 182 0 1 1039 1 20 25 3 24 ... |
| correct output |
|---|
| 1039 |
| user output |
|---|
| 1039 |
Test 30
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 586 0 1 1099 1 18 32 26 44 ... |
| correct output |
|---|
| 1099 |
| user output |
|---|
| 1099 |
Test 31
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 486 0 1 1818 1 13 44 7 43 ... |
| correct output |
|---|
| 1818 |
| user output |
|---|
| 1818 |
Test 32
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 2000 0 1 1679 1 4 45 16 38 ... |
| correct output |
|---|
| 1679 |
| user output |
|---|
| 1679 |
Test 33
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 2000 0 1 1999 1 26 58 32 54 ... |
| correct output |
|---|
| 32 |
| user output |
|---|
| 32 |
Test 34
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 1072 18342 859 530 340 1662 444 840 138 1101 ... |
| correct output |
|---|
| 3 |
| user output |
|---|
| 3 |
Test 35
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 1998 21857 1560 1143 456 1062 1406 1134 493 1223 ... |
| correct output |
|---|
| 4 |
| user output |
|---|
| 4 |
Test 36
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 1938 19374 506 706 489 740 1275 106 428 209 ... |
| correct output |
|---|
| 2 |
| user output |
|---|
| 2 |
Test 37
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 1997 29997 1764 629 1100 167 1684 957 1490 105 ... |
| correct output |
|---|
| 3 |
| user output |
|---|
| 3 |
Test 38
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 30000 18 1452 1182 1737 1105 842 872 232 ... |
| correct output |
|---|
| 3 |
| user output |
|---|
| 3 |
Test 39
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 30000 1998 2 1 1 0 3 1999 1 ... |
| correct output |
|---|
| 3 |
| user output |
|---|
| 3 |
Test 40
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 1999 30000 1997 2 1 1 0 3 1998 1 ... |
| correct output |
|---|
| 4 |
| user output |
|---|
| 4 |
Test 41
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 30000 0 2 1999 1 1998 3 3 5 ... |
| correct output |
|---|
| 2892 |
| user output |
|---|
| 2892 |
Test 42
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 30000 0 2 1607 1 1998 3 3 5 ... |
| correct output |
|---|
| 3340 |
| user output |
|---|
| 3340 |
Test 43
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2000 30000 0 1 1999 1 1998 1 1998 1 ... |
| correct output |
|---|
| 1999 |
| user output |
|---|
| (empty) |
Test 44
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 30000 0 1 1679 1 11 111 30 73 ... |
| correct output |
|---|
| 1679 |
| user output |
|---|
| 1679 |
Test 45
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2000 30000 0 1 1999 1 136 241 60 205 ... |
| correct output |
|---|
| 9 |
| user output |
|---|
| 9 |
Test 46
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 12345 24321 10073 2306 9631 1444 4511 2266 2440 1738 ... |
| correct output |
|---|
| 6 |
| user output |
|---|
| 6 |
Test 47
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 23221 22370 19215 23255 2243 2534 12921 13851 13997 18633 ... |
| correct output |
|---|
| -1 |
| user output |
|---|
| -1 |
Test 48
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 21193 29373 12730 16949 2962 10542 3218 29083 1118 24647 ... |
| correct output |
|---|
| 25 |
| user output |
|---|
| 25 |
Test 49
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 15297 22617 2947 25356 8121 8001 2834 21377 1882 8668 ... |
| correct output |
|---|
| 31 |
| user output |
|---|
| 31 |
Test 50
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 30000 30000 20832 10056 23055 12297 9466 24054 427 8139 ... |
| correct output |
|---|
| 35 |
| user output |
|---|
| 35 |
Test 51
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 30000 30000 29998 2 1 1 0 3 29999 1 ... |
| correct output |
|---|
| 28 |
| user output |
|---|
| 28 |
Test 52
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 30000 30000 29998 2 1 1 0 3 29999 1 ... |
| correct output |
|---|
| 23851 |
| user output |
|---|
| 23851 |
Test 53
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 29999 2 110 2 17 2 |
| correct output |
|---|
| -1 |
| user output |
|---|
| -1 |
Test 54
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 30000 4 29998 2 1 1 0 3 29999 1 |
| correct output |
|---|
| -1 |
| user output |
|---|
| -1 |
Test 55
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 30000 30000 0 1 29999 1 25731 1 29123 1 ... |
| correct output |
|---|
| 29999 |
| user output |
|---|
| (empty) |
Test 56
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 30000 2471 1 2 0 29997 20232 31 26226 31 ... |
| correct output |
|---|
| 53 |
| user output |
|---|
| 53 |
Test 57
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 30000 30000 0 2 29999 1 29998 3 1 9 ... |
| correct output |
|---|
| 54996 |
| user output |
|---|
| (empty) |
Test 58
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 30000 30000 0 2 29999 1 29998 3 1 5 ... |
| correct output |
|---|
| 56832 |
| user output |
|---|
| 56832 |
Test 59
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 30000 30000 0 2 29999 1 29998 3 1 5 ... |
| correct output |
|---|
| 56832 |
| user output |
|---|
| 56832 |
Test 60
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 30000 30000 0 2 24989 1 29998 3 1 5 ... |
| correct output |
|---|
| 45814 |
| user output |
|---|
| 45814 |
Test 61
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 30000 30000 6605 8395 0 1 20018 29999 15431 29999 ... |
| correct output |
|---|
| 417046 |
| user output |
|---|
| 417046 |
Test 62
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 30000 30000 0 1 29999 1 29997 2 3 1 ... |
| correct output |
|---|
| 29998 |
| user output |
|---|
| (empty) |
Test 63
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 30000 30000 0 1 28252 1 111 592 397 568 ... |
| correct output |
|---|
| 28252 |
| user output |
|---|
| 28252 |
Test 64
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 30000 30000 0 1 19226 1 50 299 205 353 ... |
| correct output |
|---|
| 19226 |
| user output |
|---|
| 19226 |
Test 65
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 30000 30000 0 1 16189 1 47 336 236 331 ... |
| correct output |
|---|
| 16189 |
| user output |
|---|
| 16189 |
Test 66
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 30000 30000 0 1 27719 1 100 204 43 85 ... |
| correct output |
|---|
| 27719 |
| user output |
|---|
| 27719 |
Test 67
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 30000 30000 0 1 29999 1 126 187 57 231 ... |
| correct output |
|---|
| 123 |
| user output |
|---|
| 123 |