oj.uz

Submission #948591

# Submission time Handle Problem Language Result Execution time Memory
948591 2024-03-18T08:07:50 Z steveonalex Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 159 ms 262144 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ll mask){return __builtin_ctzll(mask);}
int logOf(ll mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T& container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }
 
const int N = 3e4 + 69;
const int INF = 1e9 + 69;
 
int n, m;
vector<int> a[N];
bool activated[N];
vector<int> pos[N], di[N];
 
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
    vector<pair<int, int>> dog(m);
    for(int i = 0; i<m; ++i){
        cin >> dog[i].first >> dog[i].second;
        minimize(dog[i].second, n);
    }
 
    pair<int, int> dog0 = dog[0], dog1 = dog[1];
 
    remove_dup(dog);
 
    for(auto i: dog) a[i.first].push_back(i.second);
    for(int i = 1; i<=n; ++i) {
        for(int j = 0; j<n; ++j) pos[i].push_back(j);
        di[i].resize(pos[i].size(), INF);
    }
    // for(auto i: dog) pos[i.second].push_back(i.first % i.second);
    // for(int i = 1; i<=n; ++i){
    //     vector<int> sigma = pos[i]; pos[i].clear();
    //     remove_dup(sigma);
    //     for(int j: sigma){
    //         for(int k = j; k < n; k += i) pos[i].push_back(k);
    //     }
    //     sort(ALL(pos[i]));
    //     di[i].resize(pos[i].size(), INF);
    // }
 
    int o_cnt = 0;
    int ans = INF;
    deque<pair<int, int>> q;
    q.push_back(dog0); 
    di[dog0.second][dog0.first] = 0;
    while(q.size()){
        pair<int, int> u = q.front(); q.pop_front();
        int d = di[u.second][u.first];
 
        o_cnt++;
        if (o_cnt > 6e6) exit(1);
 
        if (u.first == dog1.first) {
            minimize(ans, d);
            break;
        }
 
        for(int i = -u.second; i <= u.second; i += u.second * 2) {
            pair<int, int> v = {u.first + i, u.second};
            if (v.first < 0 || v.first >= n) continue;
            if (v.second < 1 || v.second > n) exit(1);
            if (minimize(di[v.second][v.first], d + 1)) 
                q.push_back(v);
        }
        if (!activated[u.first]){
            activated[u.first] = true;
            for(int j: a[u.first]){
                for(int i = -j; i <= j; i += j * 2) {
                    pair<int, int> v = {u.first + i, j};
                    if (v.first < 0 || v.first >= n) continue;
                    if (v.second < 1 || v.second > n) exit(1);
                    if (minimize(di[v.second][v.first], d + 1)) 
                        q.push_back(v);
                }
            }
        }
    }
 
    if (ans == INF) cout << -1 << "\n";
    else cout << ans << "\n";
 
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 2 ms 2648 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 2 ms 2652 KB Output is correct
16 Correct 2 ms 2908 KB Output is correct
17 Correct 4 ms 7772 KB Output is correct
18 Correct 21 ms 28492 KB Output is correct
19 Correct 28 ms 34136 KB Output is correct
20 Correct 33 ms 34324 KB Output is correct
21 Correct 3 ms 3932 KB Output is correct
22 Correct 28 ms 29268 KB Output is correct
23 Correct 24 ms 25436 KB Output is correct
24 Correct 25 ms 31832 KB Output is correct
25 Correct 35 ms 34272 KB Output is correct
26 Correct 34 ms 34140 KB Output is correct
27 Correct 25 ms 34140 KB Output is correct
28 Correct 28 ms 34396 KB Output is correct
29 Correct 25 ms 34128 KB Output is correct
30 Correct 31 ms 34220 KB Output is correct
31 Correct 31 ms 34140 KB Output is correct
32 Correct 25 ms 34140 KB Output is correct
33 Correct 24 ms 34396 KB Output is correct
34 Correct 21 ms 34392 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 2 ms 2672 KB Output is correct
16 Correct 2 ms 2908 KB Output is correct
17 Correct 6 ms 7768 KB Output is correct
18 Correct 21 ms 28508 KB Output is correct
19 Correct 26 ms 34208 KB Output is correct
20 Correct 26 ms 34228 KB Output is correct
21 Correct 3 ms 3932 KB Output is correct
22 Correct 24 ms 29276 KB Output is correct
23 Correct 26 ms 25436 KB Output is correct
24 Correct 31 ms 31828 KB Output is correct
25 Correct 28 ms 34396 KB Output is correct
26 Correct 25 ms 34140 KB Output is correct
27 Correct 25 ms 34140 KB Output is correct
28 Correct 26 ms 34396 KB Output is correct
29 Correct 21 ms 34140 KB Output is correct
30 Correct 24 ms 34140 KB Output is correct
31 Correct 26 ms 34140 KB Output is correct
32 Correct 25 ms 34140 KB Output is correct
33 Correct 20 ms 34396 KB Output is correct
34 Correct 25 ms 34396 KB Output is correct
35 Correct 23 ms 23384 KB Output is correct
36 Correct 14 ms 17756 KB Output is correct
37 Correct 24 ms 33104 KB Output is correct
38 Correct 30 ms 34652 KB Output is correct
39 Correct 25 ms 34648 KB Output is correct
40 Correct 27 ms 34652 KB Output is correct
41 Correct 26 ms 34544 KB Output is correct
42 Correct 22 ms 34384 KB Output is correct
43 Correct 24 ms 34384 KB Output is correct
44 Correct 22 ms 34396 KB Output is correct
45 Correct 34 ms 35164 KB Output is correct
46 Correct 27 ms 34988 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 2 ms 2648 KB Output is correct
15 Correct 2 ms 2652 KB Output is correct
16 Correct 1 ms 2904 KB Output is correct
17 Correct 5 ms 7772 KB Output is correct
18 Correct 20 ms 28508 KB Output is correct
19 Correct 25 ms 34168 KB Output is correct
20 Correct 26 ms 34392 KB Output is correct
21 Correct 4 ms 3928 KB Output is correct
22 Correct 21 ms 29276 KB Output is correct
23 Correct 19 ms 25336 KB Output is correct
24 Correct 26 ms 31908 KB Output is correct
25 Correct 25 ms 34320 KB Output is correct
26 Correct 25 ms 34140 KB Output is correct
27 Correct 25 ms 34140 KB Output is correct
28 Correct 26 ms 34220 KB Output is correct
29 Correct 20 ms 34140 KB Output is correct
30 Correct 30 ms 34140 KB Output is correct
31 Correct 26 ms 34244 KB Output is correct
32 Correct 28 ms 34268 KB Output is correct
33 Correct 20 ms 34140 KB Output is correct
34 Correct 19 ms 34396 KB Output is correct
35 Correct 19 ms 23132 KB Output is correct
36 Correct 17 ms 18004 KB Output is correct
37 Correct 23 ms 33252 KB Output is correct
38 Correct 25 ms 34640 KB Output is correct
39 Correct 25 ms 34648 KB Output is correct
40 Correct 32 ms 34680 KB Output is correct
41 Correct 25 ms 34648 KB Output is correct
42 Correct 21 ms 34440 KB Output is correct
43 Correct 21 ms 34396 KB Output is correct
44 Correct 22 ms 34652 KB Output is correct
45 Correct 30 ms 35164 KB Output is correct
46 Correct 27 ms 35164 KB Output is correct
47 Runtime error 159 ms 262144 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -