oj.uz

Submission #886534

# Submission time Handle Problem Language Result Execution time Memory
886534 2023-12-12T09:41:58 Z vjudge1 Towers (NOI22_towers) C++17
18 / 100
 821 ms 121168 KB 
#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B>
string to_string(pair<A, B>);
string to_string(string S) {
  return '"' + S + '"';
}
string to_string(const char* c) {
  return to_string(string(c));
}
string to_string(bool b) {
  return (b ? "true" : "false");
}
template<size_t T>
string to_string(bitset<T> bs) {
  return bs.to_string();
}
string to_string(vector<bool> v) {
  string res = "{";
  for (int i = 0; i < int(v.size()); ++i) {
    if (int(res.size()) > 1) {
      res += ", ";
    }
    res += to_string(v[i]);
  }
  return res + "}";
}
template<typename T>
string to_string(T v) {
  string res = "{";
  for (auto e : v) {
    if (int(res.size()) > 1) {
      res += ", ";
    }
    res += to_string(e);
  }
  return res + "}";
}
template<typename A, typename B>
string to_string(pair<A, B> p) {
  return '(' + to_string(p.first) + ", " + to_string(p.second) + ')';
}
void debug_out() {
  cerr << endl;
}
template<typename H, typename... T>
void debug_out(H head, T... tail) {
  cerr << "  " << to_string(head);
  debug_out(tail...);
}

#ifdef DEBUG 
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) 
#else 
  #define debug(...) void(37)
#endif

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int> X(N), Y(N);
  for (int i = 0; i < N; ++i) {
    cin >> X[i] >> Y[i];
    --X[i], --Y[i];
  }
  #ifdef LOCAL
    const int MAX = int(30);
  #else
    const int MAX = int(1e6);
  #endif
  vector<vector<int>> xs(MAX), ys(MAX);
  for (int i = 0; i < N; ++i) {
    xs[X[i]].push_back(i);
    ys[Y[i]].push_back(i);
  }
  vector<int> xid(N), yid(N);
  for (int i = 0; i < MAX; ++i) {
    sort(xs[i].begin(), xs[i].end(), [&](int x, int y) {  
      return Y[x] < Y[y];
    });
    sort(ys[i].begin(), ys[i].end(), [&](int x, int y) {
      return X[x] < X[y];
    });
    for (int j = 0; j < int(xs[i].size()); ++j) {
      xid[xs[i][j]] = j;
    }
    for (int j = 0; j < int(ys[i].size()); ++j) {
      yid[ys[i][j]] = j;
    }
  }
  vector<bool> used(N), only(N);
  for (int i = 0; i < MAX; ++i) {
    if (xs[i].empty()) continue;
    used[xs[i][0]] = true;
    used[xs[i].back()] = true;
    if (xs[i].size() == 1) {
      only[xs[i][0]] = true;
    }
  }
  debug(used);
  for (int i = MAX - 1; i > 0; --i) {
    vector<int> act;
    for (auto x : ys[i]) {
      if (used[x]) {
        act.push_back(x);
      }
    }
    debug(act);
    for (int j = 1; j < int(act.size()) - 1; ++j) {
      int e = act[j];
      used[e] = false;
      debug(e);
      if (!only[e]) {
        debug(xs[X[e]]);
        int prev = xid[e] - 1;
        if (prev >= 0) {
          int go = xs[X[e]][prev];
          if (used[go]) {
            only[go] = true;
          } else {
            used[go] = true;
          }
        }
      }
    }
  }
  debug(used);
  for (int i = 0; i < MAX; ++i) {
    vector<int> act;
    for (auto x : ys[i]) {
      if (used[x]) {
        act.push_back(x);
      }
    }
    for (int j = 1; j < int(act.size()) - 1; ++j) {
      int e = act[j];
      used[e] = false;
      if (!only[e]) {
        int prev = xid[e]  + 1;
        assert(prev < int(xs[X[e]].size()));
        int go = xs[X[e]][prev];
        if (used[go]) {
          only[go] = true;
        } else {
          used[go] = true;
        }
      }
    }
  }
  for (int i = 0; i < N; ++i) {
    cout << used[i];
  }
  cout << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47196 KB Output is correct
2 Correct 23 ms 47192 KB Output is correct
3 Correct 20 ms 47440 KB Output is correct
4 Correct 20 ms 47196 KB Output is correct
5 Correct 21 ms 47196 KB Output is correct
6 Correct 24 ms 47196 KB Output is correct
7 Correct 20 ms 47196 KB Output is correct
8 Correct 21 ms 47196 KB Output is correct
9 Correct 22 ms 47420 KB Output is correct
10 Correct 21 ms 47196 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47196 KB Output is correct
2 Correct 23 ms 47192 KB Output is correct
3 Correct 20 ms 47440 KB Output is correct
4 Correct 20 ms 47196 KB Output is correct
5 Correct 21 ms 47196 KB Output is correct
6 Correct 24 ms 47196 KB Output is correct
7 Correct 20 ms 47196 KB Output is correct
8 Correct 21 ms 47196 KB Output is correct
9 Correct 22 ms 47420 KB Output is correct
10 Correct 21 ms 47196 KB Output is correct
11 Correct 21 ms 47192 KB Output is correct
12 Correct 21 ms 47196 KB Output is correct
13 Correct 21 ms 47448 KB Output is correct
14 Correct 21 ms 47436 KB Output is correct
15 Correct 21 ms 47196 KB Output is correct
16 Incorrect 21 ms 47444 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 50784 KB Output is correct
2 Correct 38 ms 51388 KB Output is correct
3 Correct 85 ms 59160 KB Output is correct
4 Correct 136 ms 70484 KB Output is correct
5 Correct 41 ms 51792 KB Output is correct
6 Correct 26 ms 48220 KB Output is correct
7 Correct 153 ms 69460 KB Output is correct
8 Correct 91 ms 62804 KB Output is correct
9 Correct 185 ms 81236 KB Output is correct
10 Correct 155 ms 74060 KB Output is correct
11 Correct 193 ms 79944 KB Output is correct
12 Correct 190 ms 79940 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 107128 KB Output is correct
2 Correct 405 ms 107104 KB Output is correct
3 Correct 447 ms 107088 KB Output is correct
4 Correct 408 ms 107100 KB Output is correct
5 Correct 409 ms 107092 KB Output is correct
6 Correct 781 ms 120656 KB Output is correct
7 Correct 800 ms 120900 KB Output is correct
8 Correct 821 ms 121168 KB Output is correct
9 Correct 792 ms 120916 KB Output is correct
10 Correct 804 ms 121164 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47196 KB Output is correct
2 Correct 23 ms 47192 KB Output is correct
3 Correct 20 ms 47440 KB Output is correct
4 Correct 20 ms 47196 KB Output is correct
5 Correct 21 ms 47196 KB Output is correct
6 Correct 24 ms 47196 KB Output is correct
7 Correct 20 ms 47196 KB Output is correct
8 Correct 21 ms 47196 KB Output is correct
9 Correct 22 ms 47420 KB Output is correct
10 Correct 21 ms 47196 KB Output is correct
11 Correct 21 ms 47192 KB Output is correct
12 Correct 21 ms 47196 KB Output is correct
13 Correct 21 ms 47448 KB Output is correct
14 Correct 21 ms 47436 KB Output is correct
15 Correct 21 ms 47196 KB Output is correct
16 Incorrect 21 ms 47444 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47196 KB Output is correct
2 Correct 23 ms 47192 KB Output is correct
3 Correct 20 ms 47440 KB Output is correct
4 Correct 20 ms 47196 KB Output is correct
5 Correct 21 ms 47196 KB Output is correct
6 Correct 24 ms 47196 KB Output is correct
7 Correct 20 ms 47196 KB Output is correct
8 Correct 21 ms 47196 KB Output is correct
9 Correct 22 ms 47420 KB Output is correct
10 Correct 21 ms 47196 KB Output is correct
11 Correct 21 ms 47192 KB Output is correct
12 Correct 21 ms 47196 KB Output is correct
13 Correct 21 ms 47448 KB Output is correct
14 Correct 21 ms 47436 KB Output is correct
15 Correct 21 ms 47196 KB Output is correct
16 Incorrect 21 ms 47444 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47196 KB Output is correct
2 Correct 23 ms 47192 KB Output is correct
3 Correct 20 ms 47440 KB Output is correct
4 Correct 20 ms 47196 KB Output is correct
5 Correct 21 ms 47196 KB Output is correct
6 Correct 24 ms 47196 KB Output is correct
7 Correct 20 ms 47196 KB Output is correct
8 Correct 21 ms 47196 KB Output is correct
9 Correct 22 ms 47420 KB Output is correct
10 Correct 21 ms 47196 KB Output is correct
11 Correct 21 ms 47192 KB Output is correct
12 Correct 21 ms 47196 KB Output is correct
13 Correct 21 ms 47448 KB Output is correct
14 Correct 21 ms 47436 KB Output is correct
15 Correct 21 ms 47196 KB Output is correct
16 Incorrect 21 ms 47444 KB Output isn't correct
17 Halted 0 ms 0 KB -