oj.uz

Submission #503289

# Submission time Handle Problem Language Result Execution time Memory
503289 2022-01-07T15:34:57 Z BERNARB01 Building Skyscrapers (CEOI19_skyscrapers) C++17
0 / 100
 3500 ms 7920 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, subtask;
  cin >> n >> subtask;
  vector<pair<int, int>> p(n);
  map<int, int> mp;
  for (int i = 0; i < n; i++) {
    cin >> p[i].first >> p[i].second;
    mp[p[i].first] = mp[p[i].second] = 0;
  }
  int idd = 0;
  for (auto& pp : mp) {
    pp.second = idd++;
  }
  vector<pair<int, int>> rp = p;
  for (int i = 0; i < n; i++) {
    p[i].first = mp[p[i].first];
    p[i].second = mp[p[i].second];
  }
  sort(p.begin(), p.end());
  vector<int> per(n);
  iota(per.begin(), per.end(), 0);
  do {
    bool bl = true;
    map<pair<int, int>, bool> vis;
    set<pair<int, int>> se;
    auto can_go = [&](int x, int y) {
      return vis[{x - 1, y - 1}] || vis[{x - 1, y}] || vis[{x - 1, y}] || vis[{x, y - 1}] || vis[{x, y + 1}] || vis[{x + 1, y - 1}] || vis[{x + 1, y}] || vis[{x + 1, y + 1}];
    };
    function<bool(int, int, int)> can_go_out = [&](int x, int y, int dph) {
      if (vis[{x, y}]) {
        return false;
      }
      if (x + 1 >= idd || y + 1 >= idd || x - 1 < 0 || y - 1 < 0) {
        return true;
      }
      if (dph == 4) {
        return !(rand() % 5 == 0);
      }
      se.insert({x, y});
      if (!se.count({x - 1, y})) {
        if (can_go_out(x - 1, y, dph + 1)) {
          return true;
        }
      }
      if (!se.count({x + 1, y})) {
        if (can_go_out(x + 1, y, dph + 1)) {
          return true;
        }
      }
      if (!se.count({x, y - 1})) {
        if (can_go_out(x, y - 1, dph + 1)) {
          return true;
        }
      }
      if (!se.count({x, y + 1})) {
        if (can_go_out(x, y + 1, dph + 1)) {
          return true;
        }
      }
      return false;
    };
    vis[{rp[per[0]].first, rp[per[0]].second}] = 1;
    for (int i = 1; i < n; i++) {
      if (!can_go(rp[per[i]].first, rp[per[i]].second)) {
        bl = false;
      }
      vis[{rp[per[i]].first, rp[per[i]].second}] = 1;
    }
    if (!bl) {
      continue;
    }
    vis.clear();
    for (int i = 0; i < n; i++) {
      while (!se.empty()) {
        se.erase(se.begin());
      }
      if (!can_go_out(p[per[i]].first, p[per[i]].second, 0)) {
        /**
        cout << i << " " << p[per[i]].first << " " << p[per[i]].second << '\n';
        for (auto pp : vis) {
          cout << pp.first.first << " " << pp.first.second << '\n';
        }
        **/
        bl = false;
        break;
      }
      vis[{p[per[i]].first, p[per[i]].second}] = 1;
    }
    if (!bl) {
      continue;
    }
    cout << "YES" << '\n';
    for (int i = 0; i < n; i++) {
      if (i > 0) {
        cout << " ";
      }
      cout << per[i] + 1;
    }
    cout << '\n';
    return 0;
  } while (next_permutation(per.begin(), per.end()));
  cout << "NO" << '\n';
  return 0;
}

Subtask #1
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 1 ms 204 KB ans=YES N=5
5 Correct 1 ms 204 KB ans=YES N=9
6 Correct 0 ms 204 KB ans=YES N=5
7 Correct 1581 ms 292 KB ans=NO N=9
8 Execution timed out 3561 ms 204 KB Time limit exceeded
9 Halted 0 ms 0 KB -

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 1 ms 204 KB ans=YES N=5
5 Correct 1 ms 204 KB ans=YES N=9
6 Correct 0 ms 204 KB ans=YES N=5
7 Correct 1581 ms 292 KB ans=NO N=9
8 Execution timed out 3561 ms 204 KB Time limit exceeded
9 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 1 ms 204 KB ans=YES N=5
5 Correct 1 ms 204 KB ans=YES N=9
6 Correct 0 ms 204 KB ans=YES N=5
7 Correct 1581 ms 292 KB ans=NO N=9
8 Execution timed out 3561 ms 204 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3582 ms 1484 KB Time limit exceeded
2 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 1 ms 204 KB ans=YES N=5
5 Correct 1 ms 204 KB ans=YES N=9
6 Correct 0 ms 204 KB ans=YES N=5
7 Correct 1581 ms 292 KB ans=NO N=9
8 Execution timed out 3561 ms 204 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3587 ms 7920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3582 ms 1484 KB Time limit exceeded
2 Halted 0 ms 0 KB -