답안 #45377 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45377	2018-04-13T05:03:07 Z	JohnTitor	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	824 ms	35464 KB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
typedef long long ll;
typedef long double ld;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "Jakarta_Skyscrapers"
int n, m;
int b[30001];
int p[30001];
vector <int> big[30001];
vector <int> small[30001];
int f[30001][176];
int sq=175;
class data{
public:
    int u, s, d;
    data(){}
    data(int _u, int _s, int _d){
        u=_u;
        s=_s;
        d=_d;
    }
};
class cmp{
public:
    bool operator ()(data a, data b){
        return a.d>b.d;
    }
};
priority_queue <data, vector <data>, cmp> q;
const int inf=mask(30);
void dij(){
    FOR(i, 0, n) FOR(j, 0, sq) f[i][j]=inf;
    f[b[0]][0]=0;
    q.push(data(b[0], 0, 0));
    data t;
    while(!q.empty()){
        t=q.top();
        q.pop();
        if(t.d>f[t.u][t.s]) continue;
//        cerr<<t.u<<" "<<t.s<<" "<<t.d<<'\n';
        if(t.s){///can move
            if(t.u-t.s>=0){
                if(f[t.u-t.s][t.s]>t.d+1){
                    f[t.u-t.s][t.s]=t.d+1;
                    q.push(data(t.u-t.s, t.s, t.d+1));
                }
            }
            if(t.u+t.s<n){
                if(f[t.u+t.s][t.s]>t.d+1){
                    f[t.u+t.s][t.s]=t.d+1;
                    q.push(data(t.u+t.s, t.s, t.d+1));
                }
            }
            if(t.d<f[t.u][0]){
                f[t.u][0]=t.d;
                q.push(data(t.u, 0, t.d));
            }
        }
        else{
            ///move using small steps:
            for(int i: small[t.u]){
                if(f[t.u][p[i]]>f[t.u][0]){
                    f[t.u][p[i]]=f[t.u][0];
                    q.push(data(t.u, p[i], f[t.u][p[i]]));
                }
            }
            ///move using big steps:
            for(int i: big[t.u]){
                for(int x=b[i]%p[i]; x<=n; x+=p[i]){
                    if(f[x][0]>f[t.u][0]+abs(t.u-x)/p[i]){
                        f[x][0]=f[t.u][0]+abs(t.u-x)/p[i];
                        q.push(data(x, 0, f[x][0]));
                    }
                }
            }
        }
    }
}
int main(){
    #ifdef Kanikou
        if(fopen(taskname".inp", "r"))
            freopen(taskname".inp", "r", stdin);
    #endif // Kanikou
    read(n);
    read(m);
    FFOR(i, 0, m){
        read(b[i]);
        read(p[i]);
        if(p[i]<sq) small[b[i]].pb(i);
        else big[b[i]].pb(i);
    }
    dij();
    int ans=f[b[1]][0];
//    for(int x=b[1]%p[1]; x<n; x+=p[1]) ans=min(ans, f[x][0]+abs(b[1]-x)/p[1]);
    if(ans==inf) ans=-1;
    writeln(ans);
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1784 KB	Output is correct
2	Correct	3 ms	1784 KB	Output is correct
3	Correct	3 ms	1836 KB	Output is correct
4	Correct	4 ms	1836 KB	Output is correct
5	Correct	3 ms	1868 KB	Output is correct
6	Correct	3 ms	1964 KB	Output is correct
7	Correct	3 ms	1968 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1972 KB	Output is correct
2	Correct	3 ms	2100 KB	Output is correct
3	Correct	4 ms	2112 KB	Output is correct
4	Correct	4 ms	2112 KB	Output is correct
5	Correct	3 ms	2112 KB	Output is correct
6	Correct	4 ms	2112 KB	Output is correct
7	Correct	4 ms	2112 KB	Output is correct
8	Correct	3 ms	2112 KB	Output is correct
9	Correct	3 ms	2112 KB	Output is correct
10	Correct	3 ms	2112 KB	Output is correct
11	Correct	4 ms	2232 KB	Output is correct
12	Correct	4 ms	2344 KB	Output is correct
13	Correct	3 ms	2344 KB	Output is correct
14	Correct	4 ms	2344 KB	Output is correct
15	Correct	4 ms	2344 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2344 KB	Output is correct
2	Correct	3 ms	2344 KB	Output is correct
3	Correct	5 ms	2344 KB	Output is correct
4	Correct	3 ms	2344 KB	Output is correct
5	Correct	4 ms	2344 KB	Output is correct
6	Correct	4 ms	2344 KB	Output is correct
7	Correct	3 ms	2344 KB	Output is correct
8	Correct	3 ms	2344 KB	Output is correct
9	Correct	3 ms	2344 KB	Output is correct
10	Correct	3 ms	2368 KB	Output is correct
11	Correct	4 ms	2408 KB	Output is correct
12	Correct	3 ms	2436 KB	Output is correct
13	Correct	3 ms	2436 KB	Output is correct
14	Correct	5 ms	2476 KB	Output is correct
15	Correct	4 ms	2492 KB	Output is correct
16	Correct	3 ms	2500 KB	Output is correct
17	Correct	5 ms	2892 KB	Output is correct
18	Correct	4 ms	3548 KB	Output is correct
19	Correct	4 ms	3816 KB	Output is correct
20	Correct	12 ms	3824 KB	Output is correct
21	Correct	4 ms	3824 KB	Output is correct
22	Correct	5 ms	3824 KB	Output is correct
23	Correct	4 ms	3824 KB	Output is correct
24	Correct	5 ms	3824 KB	Output is correct
25	Correct	5 ms	3892 KB	Output is correct
26	Correct	4 ms	3928 KB	Output is correct
27	Correct	5 ms	3940 KB	Output is correct
28	Correct	6 ms	3960 KB	Output is correct
29	Correct	8 ms	3980 KB	Output is correct
30	Correct	5 ms	3980 KB	Output is correct
31	Correct	6 ms	3992 KB	Output is correct
32	Correct	6 ms	3996 KB	Output is correct
33	Correct	14 ms	4000 KB	Output is correct
34	Correct	14 ms	4012 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4012 KB	Output is correct
2	Correct	3 ms	4012 KB	Output is correct
3	Correct	3 ms	4012 KB	Output is correct
4	Correct	3 ms	4012 KB	Output is correct
5	Correct	3 ms	4012 KB	Output is correct
6	Correct	3 ms	4012 KB	Output is correct
7	Correct	3 ms	4012 KB	Output is correct
8	Correct	4 ms	4012 KB	Output is correct
9	Correct	3 ms	4012 KB	Output is correct
10	Correct	3 ms	4012 KB	Output is correct
11	Correct	4 ms	4012 KB	Output is correct
12	Correct	3 ms	4012 KB	Output is correct
13	Correct	3 ms	4012 KB	Output is correct
14	Correct	4 ms	4012 KB	Output is correct
15	Correct	4 ms	4012 KB	Output is correct
16	Correct	4 ms	4012 KB	Output is correct
17	Correct	6 ms	4012 KB	Output is correct
18	Correct	5 ms	4012 KB	Output is correct
19	Correct	5 ms	4016 KB	Output is correct
20	Correct	6 ms	4152 KB	Output is correct
21	Correct	4 ms	4152 KB	Output is correct
22	Correct	4 ms	4152 KB	Output is correct
23	Correct	4 ms	4152 KB	Output is correct
24	Correct	6 ms	4152 KB	Output is correct
25	Correct	5 ms	4224 KB	Output is correct
26	Correct	5 ms	4244 KB	Output is correct
27	Correct	6 ms	4260 KB	Output is correct
28	Correct	6 ms	4280 KB	Output is correct
29	Correct	9 ms	4296 KB	Output is correct
30	Correct	7 ms	4296 KB	Output is correct
31	Correct	9 ms	4312 KB	Output is correct
32	Correct	8 ms	4312 KB	Output is correct
33	Correct	15 ms	4316 KB	Output is correct
34	Correct	14 ms	4328 KB	Output is correct
35	Correct	16 ms	4724 KB	Output is correct
36	Correct	6 ms	4724 KB	Output is correct
37	Correct	19 ms	5112 KB	Output is correct
38	Correct	19 ms	5656 KB	Output is correct
39	Correct	20 ms	5920 KB	Output is correct
40	Correct	19 ms	6184 KB	Output is correct
41	Correct	19 ms	6448 KB	Output is correct
42	Correct	7 ms	6460 KB	Output is correct
43	Correct	9 ms	6664 KB	Output is correct
44	Correct	10 ms	6872 KB	Output is correct
45	Correct	49 ms	7528 KB	Output is correct
46	Correct	41 ms	7792 KB	Output is correct

Subtask #5
43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	7792 KB	Output is correct
2	Correct	3 ms	7792 KB	Output is correct
3	Correct	3 ms	7792 KB	Output is correct
4	Correct	3 ms	7792 KB	Output is correct
5	Correct	3 ms	7792 KB	Output is correct
6	Correct	3 ms	7792 KB	Output is correct
7	Correct	3 ms	7792 KB	Output is correct
8	Correct	4 ms	7792 KB	Output is correct
9	Correct	3 ms	7792 KB	Output is correct
10	Correct	4 ms	7792 KB	Output is correct
11	Correct	4 ms	7792 KB	Output is correct
12	Correct	3 ms	7792 KB	Output is correct
13	Correct	3 ms	7792 KB	Output is correct
14	Correct	5 ms	7792 KB	Output is correct
15	Correct	4 ms	7792 KB	Output is correct
16	Correct	3 ms	7792 KB	Output is correct
17	Correct	5 ms	7792 KB	Output is correct
18	Correct	4 ms	7792 KB	Output is correct
19	Correct	5 ms	7792 KB	Output is correct
20	Correct	4 ms	7792 KB	Output is correct
21	Correct	3 ms	7792 KB	Output is correct
22	Correct	4 ms	7792 KB	Output is correct
23	Correct	5 ms	7792 KB	Output is correct
24	Correct	7 ms	7792 KB	Output is correct
25	Correct	5 ms	7792 KB	Output is correct
26	Correct	5 ms	7792 KB	Output is correct
27	Correct	4 ms	7792 KB	Output is correct
28	Correct	5 ms	7792 KB	Output is correct
29	Correct	10 ms	7792 KB	Output is correct
30	Correct	7 ms	7792 KB	Output is correct
31	Correct	9 ms	7792 KB	Output is correct
32	Correct	7 ms	7792 KB	Output is correct
33	Correct	13 ms	7792 KB	Output is correct
34	Correct	14 ms	7792 KB	Output is correct
35	Correct	15 ms	7792 KB	Output is correct
36	Correct	6 ms	7792 KB	Output is correct
37	Correct	25 ms	8056 KB	Output is correct
38	Correct	23 ms	8524 KB	Output is correct
39	Correct	30 ms	8788 KB	Output is correct
40	Correct	20 ms	9152 KB	Output is correct
41	Correct	19 ms	9284 KB	Output is correct
42	Correct	7 ms	9328 KB	Output is correct
43	Correct	7 ms	9532 KB	Output is correct
44	Correct	7 ms	9708 KB	Output is correct
45	Correct	43 ms	10476 KB	Output is correct
46	Correct	60 ms	10624 KB	Output is correct
47	Correct	92 ms	18136 KB	Output is correct
48	Correct	21 ms	25348 KB	Output is correct
49	Correct	22 ms	27124 KB	Output is correct
50	Correct	26 ms	28892 KB	Output is correct
51	Correct	89 ms	31504 KB	Output is correct
52	Correct	84 ms	31884 KB	Output is correct
53	Correct	37 ms	31884 KB	Output is correct
54	Correct	26 ms	31884 KB	Output is correct
55	Correct	24 ms	31884 KB	Output is correct
56	Correct	35 ms	32248 KB	Output is correct
57	Correct	100 ms	32248 KB	Output is correct
58	Correct	31 ms	32248 KB	Output is correct
59	Correct	42 ms	32248 KB	Output is correct
60	Correct	43 ms	32248 KB	Output is correct
61	Correct	37 ms	32580 KB	Output is correct
62	Correct	72 ms	33468 KB	Output is correct
63	Correct	74 ms	34556 KB	Output is correct
64	Correct	68 ms	34908 KB	Output is correct
65	Correct	296 ms	35012 KB	Output is correct
66	Correct	799 ms	35236 KB	Output is correct
67	Correct	824 ms	35464 KB	Output is correct

답안 #45377

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 14.0 / 14.0

Subtask #4 21.0 / 21.0

Subtask #5 43.0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
14.0 / 14.0

Subtask #4
21.0 / 21.0

Subtask #5
43.0 / 43.0