oj.uz

Submission #501077

# Submission time Handle Problem Language Result Execution time Memory
501077 2022-01-02T10:30:19 Z InternetPerson10 Building Skyscrapers (CEOI19_skyscrapers) C++17
8 / 100
 3500 ms 40616 KB 
#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> v;

int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dxe[4] = {-1, 0, 1, 0};
int dye[4] = {0, 1, 0, -1};

map<pair<int, int>, int> m;
set<pair<int, int>> black;

struct dsu {
    vector<int> par, siz;
    void init(int n) {
        vector<int>().swap(par);
        vector<int>().swap(siz);
        par.resize(n);
        siz.resize(n, 1);
        for(int i = 0; i < n; i++) par[i] = i;
    }
    int get(int x) {
        if(x == par[x]) return x;
        return par[x] = get(par[x]);
    }
    bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if(x == y) return false;
        if(x < y) swap(x, y); // y is the lesser one now
        par[x] = y;
        siz[y] += siz[x];
        return true;
    }
};


vector<int> find_order(int n, vector<int> x, vector<int> y) {
    vector<int> ans;
    return ans;
}

vector<int> find_best_order(int n, vector<int> x, vector<int> y) {
    vector<int> ans;
    int mix, miy;
    mix = miy = 1234567890;
    for(int i = 0; i < n; i++) {
        mix = min(mix, x[i]);
        miy = min(miy, y[i]);
    }
    mix--;
    miy--;
    for(int i = 0; i < n; i++) {
        x[i] -= mix;
        y[i] -= miy;
        v.push_back({x[i], y[i]});
        black.insert({x[i], y[i]});
        for(int j = 0; j < 8; j++) {
            v.push_back({x[i]+dx[j], y[i]+dy[j]});
        }
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    // Vertex labels are stored as an unordered_map
    // I should constopt this if it's too slow
    for(int i = 0; i < v.size(); i++) {
        m[v[i]] = i;
    }
    dsu uf;
    uf.init(v.size()+1);
    // First check if the peple are connected
    bool ok = false;
    for(int i = 0; i < v.size(); i++) {
        if(black.count(v[i])) {
            for(int j = 0; j < 8; j++) {
                pair<int, int> oth_pair = {v[i].first+dx[j], v[i].second+dy[j]};
                if(black.count(oth_pair)) {
                    uf.unite(m[v[i]], m[oth_pair]);
                }
            }
            if(uf.siz[uf.get(m[v[i]])] == n) ok = true;
        }
    }
    if(!ok) return ans;
    // Now find an order, unite all white regions
    uf.init(v.size()+1);
    for(int i = 0; i < v.size(); i++) {
        if(black.count(v[i])) continue;
        for(int j = 0; j < 4; j++) {
            pair<int, int> oth_pair = {v[i].first+dxe[j], v[i].second+dye[j]};
            if(black.count(oth_pair)) continue;
            uf.unite(m[v[i]], m[oth_pair]);
        }
    }
    ans.reserve(n);
    for(int z = 0; z < n; z++) {
        for(int i = 0; i < n; i++) { // Checks if the regions around the cell are "good"
            pair<int, int> this_pair = {x[i], y[i]};
            // cout << x[i] << ' ' << y[i] << '\n';
            if(!black.count(this_pair)) continue;
            vector<int> regs;
            for(int j = 0; j < 4; j++) {
                pair<int, int> oth_pair = {x[i]+dxe[j], y[i]+dye[j]};
                if(black.count(oth_pair)) regs.push_back(-1); 
                else regs.push_back(uf.get(m[oth_pair]));
                oth_pair = {x[i]+dx[(2*j+2)%8], y[i]+dy[(2*j+2)%8]};
                if(black.count(oth_pair)) regs.push_back(-1);
            }
            /*
            cout << z << ' ' << i << " | ";
            for(int g : regs) cout << g << ' ';
            cout << '\n';
            */
            while(regs[0] == regs.back() && regs.size() > 1) regs.pop_back();
            regs.erase(unique(regs.begin(), regs.end()), regs.end());
            regs.erase(remove(regs.begin(), regs.end(), -1), regs.end());
            if(regs.size() == 1 && regs[0] == 0) {
                black.erase(this_pair);
                ans.push_back(i+1);
                uf.unite(m[this_pair], 0);
                break;
            }
            if(regs.size() == 1) continue;
            sort(regs.begin(), regs.end());
            /*
            for(int g : regs) cout << g << ' ';
            cout << '\n';
            */
            if(regs[0] != 0) continue;
            bool ok = true;
            for(int i = 1; i < regs.size(); i++) {
                if(regs[i] == regs[i-1]) ok = false;
            }
            if(!ok) continue;
            black.erase(this_pair);
            ans.push_back(i+1);
            uf.unite(m[this_pair], 0);
            for(int i = 1; i < regs.size(); i++) {
                uf.unite(regs[i-1], regs[i]);
            }
            break;
        }
        if(ans.size() == z-1) {
            vector<int>().swap(ans);
            return ans;
        }
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

int main() {
    int n, s;
    cin >> n >> s;
    vector<int> x(n), y(n);
    for(int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    vector<int> ans;
    if(s == 1) ans = find_best_order(n, x, y);
    if(s == 2) ans = find_best_order(n, x, y);
    if(ans.size() == 0) {
        cout << "NO\n";
    }
    else {
        cout << "YES\n";
        for(int i = 0; i < ans.size(); i++) cout << ans[i] << '\n';
    }
}

Compilation message

skyscrapers.cpp: In function 'std::vector<int> find_best_order(int, std::vector<int>, std::vector<int>)':
skyscrapers.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 0; i < v.size(); i++) {
      |                    ~~^~~~~~~~~~
skyscrapers.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i = 0; i < v.size(); i++) {
      |                    ~~^~~~~~~~~~
skyscrapers.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0; i < v.size(); i++) {
      |                    ~~^~~~~~~~~~
skyscrapers.cpp:133:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |             for(int i = 1; i < regs.size(); i++) {
      |                            ~~^~~~~~~~~~~~~
skyscrapers.cpp:140:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |             for(int i = 1; i < regs.size(); i++) {
      |                            ~~^~~~~~~~~~~~~
skyscrapers.cpp:145:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  145 |         if(ans.size() == z-1) {
      |            ~~~~~~~~~~~^~~~~~
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:169:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |         for(int i = 0; i < ans.size(); i++) cout << ans[i] << '\n';
      |                        ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB ans=YES N=1
2 Correct 0 ms 204 KB ans=YES N=4
3 Correct 0 ms 204 KB ans=NO N=4
4 Correct 0 ms 204 KB ans=YES N=5
5 Correct 1 ms 204 KB ans=YES N=9
6 Correct 1 ms 204 KB ans=YES N=5
7 Correct 1 ms 204 KB ans=NO N=9
8 Correct 0 ms 204 KB ans=NO N=10
9 Correct 1 ms 292 KB ans=YES N=10
10 Correct 1 ms 204 KB ans=YES N=10
11 Correct 1 ms 204 KB ans=YES N=10
12 Correct 1 ms 204 KB ans=YES N=9
13 Correct 1 ms 204 KB ans=YES N=9
14 Correct 1 ms 204 KB ans=YES N=8
15 Correct 0 ms 204 KB ans=YES N=8
16 Correct 0 ms 204 KB ans=NO N=2

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB ans=YES N=1
2 Correct 0 ms 204 KB ans=YES N=4
3 Correct 0 ms 204 KB ans=NO N=4
4 Correct 0 ms 204 KB ans=YES N=5
5 Correct 1 ms 204 KB ans=YES N=9
6 Correct 1 ms 204 KB ans=YES N=5
7 Correct 1 ms 204 KB ans=NO N=9
8 Correct 0 ms 204 KB ans=NO N=10
9 Correct 1 ms 292 KB ans=YES N=10
10 Correct 1 ms 204 KB ans=YES N=10
11 Correct 1 ms 204 KB ans=YES N=10
12 Correct 1 ms 204 KB ans=YES N=9
13 Correct 1 ms 204 KB ans=YES N=9
14 Correct 1 ms 204 KB ans=YES N=8
15 Correct 0 ms 204 KB ans=YES N=8
16 Correct 0 ms 204 KB ans=NO N=2
17 Correct 0 ms 204 KB ans=YES N=17
18 Incorrect 1 ms 204 KB Contestant did not find solution
19 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB ans=YES N=1
2 Correct 0 ms 204 KB ans=YES N=4
3 Correct 0 ms 204 KB ans=NO N=4
4 Correct 0 ms 204 KB ans=YES N=5
5 Correct 1 ms 204 KB ans=YES N=9
6 Correct 1 ms 204 KB ans=YES N=5
7 Correct 1 ms 204 KB ans=NO N=9
8 Correct 0 ms 204 KB ans=NO N=10
9 Correct 1 ms 292 KB ans=YES N=10
10 Correct 1 ms 204 KB ans=YES N=10
11 Correct 1 ms 204 KB ans=YES N=10
12 Correct 1 ms 204 KB ans=YES N=9
13 Correct 1 ms 204 KB ans=YES N=9
14 Correct 1 ms 204 KB ans=YES N=8
15 Correct 0 ms 204 KB ans=YES N=8
16 Correct 0 ms 204 KB ans=NO N=2
17 Correct 0 ms 204 KB ans=YES N=17
18 Incorrect 1 ms 204 KB Contestant did not find solution
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1736 KB ans=NO N=1934
2 Correct 6 ms 840 KB ans=NO N=1965
3 Incorrect 394 ms 828 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 2)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB ans=YES N=1
2 Correct 0 ms 204 KB ans=YES N=4
3 Correct 0 ms 204 KB ans=NO N=4
4 Correct 0 ms 204 KB ans=YES N=5
5 Correct 1 ms 204 KB ans=YES N=9
6 Correct 1 ms 204 KB ans=YES N=5
7 Correct 1 ms 204 KB ans=NO N=9
8 Correct 0 ms 204 KB ans=NO N=10
9 Correct 1 ms 292 KB ans=YES N=10
10 Correct 1 ms 204 KB ans=YES N=10
11 Correct 1 ms 204 KB ans=YES N=10
12 Correct 1 ms 204 KB ans=YES N=9
13 Correct 1 ms 204 KB ans=YES N=9
14 Correct 1 ms 204 KB ans=YES N=8
15 Correct 0 ms 204 KB ans=YES N=8
16 Correct 0 ms 204 KB ans=NO N=2
17 Correct 0 ms 204 KB ans=YES N=17
18 Incorrect 1 ms 204 KB Contestant did not find solution
19 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 16396 KB ans=NO N=66151
2 Correct 290 ms 40616 KB ans=NO N=64333
3 Execution timed out 3563 ms 14496 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1736 KB ans=NO N=1934
2 Correct 6 ms 840 KB ans=NO N=1965
3 Incorrect 394 ms 828 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 2)
4 Halted 0 ms 0 KB -