Submission #1032061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032061		vjudge1	Line Town (CCO23_day1problem3)	C++17	0 / 25	298 ms	673660 KiB

Main

#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
• Subtask 2: 0 / 3
• Subtask 3: 0 / 3
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 3
• Subtask 7: 0 / 2
• Subtask 8: 0 / 3