oj.uz

Submission #948582

# Submission time Handle Problem Language Result Execution time Memory
948582 2024-03-18T08:03:14 Z steveonalex Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 171 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;
    }
 
    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 = 0; i<N; ++i) {
        for(int j = 0; j<n; ++j) pos[i].push_back(j);
        di[i].resize(pos[i].size() + 100, 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 12 ms 16472 KB Output is correct
2 Correct 10 ms 15708 KB Output is correct
3 Correct 12 ms 16512 KB Output is correct
4 Correct 13 ms 16988 KB Output is correct
5 Correct 13 ms 18012 KB Output is correct
6 Correct 17 ms 18012 KB Output is correct
7 Correct 16 ms 18008 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16476 KB Output is correct
2 Correct 10 ms 15704 KB Output is correct
3 Correct 12 ms 16512 KB Output is correct
4 Correct 12 ms 16944 KB Output is correct
5 Correct 16 ms 18012 KB Output is correct
6 Correct 13 ms 18012 KB Output is correct
7 Correct 13 ms 18012 KB Output is correct
8 Correct 19 ms 26968 KB Output is correct
9 Correct 21 ms 29788 KB Output is correct
10 Correct 29 ms 41940 KB Output is correct
11 Correct 26 ms 42072 KB Output is correct
12 Correct 27 ms 42076 KB Output is correct
13 Correct 27 ms 42104 KB Output is correct
14 Correct 28 ms 42076 KB Output is correct
15 Correct 33 ms 42068 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16476 KB Output is correct
2 Correct 9 ms 15708 KB Output is correct
3 Correct 11 ms 16476 KB Output is correct
4 Correct 13 ms 17024 KB Output is correct
5 Correct 14 ms 18096 KB Output is correct
6 Correct 15 ms 18012 KB Output is correct
7 Correct 14 ms 18012 KB Output is correct
8 Correct 20 ms 26836 KB Output is correct
9 Correct 21 ms 29788 KB Output is correct
10 Correct 26 ms 42064 KB Output is correct
11 Correct 29 ms 42076 KB Output is correct
12 Correct 26 ms 41924 KB Output is correct
13 Correct 31 ms 42068 KB Output is correct
14 Correct 26 ms 42020 KB Output is correct
15 Correct 28 ms 41968 KB Output is correct
16 Correct 58 ms 68700 KB Output is correct
17 Correct 137 ms 222804 KB Output is correct
18 Runtime error 171 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16476 KB Output is correct
2 Correct 9 ms 15536 KB Output is correct
3 Correct 18 ms 16472 KB Output is correct
4 Correct 12 ms 16912 KB Output is correct
5 Correct 13 ms 18012 KB Output is correct
6 Correct 15 ms 17976 KB Output is correct
7 Correct 18 ms 18004 KB Output is correct
8 Correct 19 ms 26972 KB Output is correct
9 Correct 20 ms 29848 KB Output is correct
10 Correct 34 ms 42076 KB Output is correct
11 Correct 27 ms 42076 KB Output is correct
12 Correct 27 ms 42068 KB Output is correct
13 Correct 26 ms 42068 KB Output is correct
14 Correct 26 ms 42072 KB Output is correct
15 Correct 40 ms 42132 KB Output is correct
16 Correct 49 ms 68692 KB Output is correct
17 Correct 123 ms 222864 KB Output is correct
18 Runtime error 138 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16728 KB Output is correct
2 Correct 9 ms 15728 KB Output is correct
3 Correct 12 ms 16512 KB Output is correct
4 Correct 13 ms 16988 KB Output is correct
5 Correct 17 ms 18012 KB Output is correct
6 Correct 13 ms 17924 KB Output is correct
7 Correct 14 ms 18012 KB Output is correct
8 Correct 20 ms 26972 KB Output is correct
9 Correct 22 ms 29808 KB Output is correct
10 Correct 30 ms 42076 KB Output is correct
11 Correct 27 ms 42088 KB Output is correct
12 Correct 28 ms 42120 KB Output is correct
13 Correct 33 ms 42264 KB Output is correct
14 Correct 35 ms 42116 KB Output is correct
15 Correct 36 ms 42156 KB Output is correct
16 Correct 53 ms 68792 KB Output is correct
17 Correct 134 ms 222836 KB Output is correct
18 Runtime error 171 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -