oj.uz

Submission #1032061

# Submission time Handle Problem Language Result Execution time Memory
1032061 2024-07-23T10:43:17 Z vjudge1 Line Town (CCO23_day1problem3) C++17
0 / 25
 298 ms 673660 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5+5;

int t, n, a[N], adj[N];
pair<int, int> b[N];
deque<int> q[2][N];
bitset<N> vis;

void dfs(int x) {
  vis[x] = 1;
  if (adj[x] != -1 && !vis[adj[x]]) dfs(adj[x]);
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  for (int i = 0; i < n; i++) {
    adj[i] = -1;

    cin >> a[i];
    b[i] = make_pair(abs(a[i]), i);
  }
  sort(b, b+n);

  int idx = 0;
  for (int i = 0; i < n; i++) {
    if (i && b[i].first > b[i-1].first) idx++;
    
    int x = b[i].second;
    if (a[x] < 0) q[0][idx].push_back(x);
    else q[1][idx].push_back(x);
  }

  int L = 0;
  int R = n-1;
  while (idx >= 0) {
    while (!q[0][idx].empty() && q[0][idx].front() == L) {
      q[0][idx].pop_front();
      L++;
    }

    while (!q[1][idx].empty() && q[1][idx].back() == R) {
      q[1][idx].pop_back();
      R--;
    }

    while (!q[0][idx].empty()) {
      adj[q[0][idx].back()] = R;
      q[0][idx].pop_back();
      R--;
    }

    while (!q[1][idx].empty()) {
      adj[q[1][idx].front()] = L;
      q[1][idx].pop_front();
      L++;
    }

    idx--;
  }

  for (int i = 0; i < n; i++) {
    if (adj[i] == i) {
      cout << "-1\n";
      return 0;
    }
  }

  int ans = n;
  for (int i = 0; i < n; i++) {
    if (vis[i]) continue;

    ans--;
    dfs(i);
  }
  cout << ans << "\n";
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 673660 KB Output is correct
2 Incorrect 298 ms 673416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 673660 KB Output is correct
2 Incorrect 298 ms 673416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 673660 KB Output is correct
2 Incorrect 298 ms 673416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 673660 KB Output is correct
2 Incorrect 298 ms 673416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 673568 KB Output is correct
2 Incorrect 260 ms 673616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 673568 KB Output is correct
2 Incorrect 260 ms 673616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 673660 KB Output is correct
2 Incorrect 298 ms 673416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 673660 KB Output is correct
2 Incorrect 298 ms 673416 KB Output isn't correct
3 Halted 0 ms 0 KB -