QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1241#771919#7861. Inverse Topological SortcaijianhongcaijianhongSuccess!2024-11-22 19:52:292024-11-22 19:52:30

Details

Extra Test:

Time Limit Exceeded

input:

100000
100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 99953 9995...

output:


result:


IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#771919#7861. Inverse Topological SortcaijianhongTL 61ms9552kbC++232.1kb2024-11-22 16:18:202024-11-22 19:55:23

answer

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
int n, deg[100010], m;
basic_string<int> g[100010];
vector<int> toposort(int op) {
  // op == -1 min
  // op == 1 max
  priority_queue<int> q;
  vector<int> ret;
  for (int i = 1; i <= n; i++) deg[i] = 0;
  for (int i = 1; i <= n; i++) for (int v : g[i]) deg[v] += 1;
  for (int i = 1; i <= n; i++) if (!deg[i]) q.push(i * op);
  while (!q.empty()) {
    int u = q.top() * op; q.pop();
    ret.push_back(u);
    for (int v : g[u]) if (--deg[v] == 0) q.push(v * op);
  }
  return ret;
}
vector<int> a, b;
void solvea(int l, int r) {
  if (l >= r) return ;
  int lst = a[l], pre = l, llst = -1;
  for (int i = l + 1; i < r; i++) {
    if (lst > a[i]) {
      if (llst == -1 || llst < a[i]) g[lst] += a[i], llst = a[i];
    }
    else solvea(pre + 1, i), lst = a[i], pre = i, llst = -1;
  }
  solvea(pre + 1, r);
}
void solveb(int l, int r) {
  if (l >= r) return ;
  int lst = b[l], pre = l, llst = -1;
  for (int i = l + 1; i < r; i++) {
    if (lst < b[i]) {
      if (llst == -1 || llst > b[i]) g[lst] += b[i], llst = b[i];
    } else solveb(pre + 1, i), lst = b[i], pre = i, llst = -1;
  }
  solveb(pre + 1, r);
}
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);
#endif
  cin >> n;
  a.resize(n);
  b.resize(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) cin >> b[i];
  solvea(0, n);
  solveb(0, n);
#ifdef LOCAL
  for (int i = 1; i <= n; i++) for (int v : g[i]) cout << i << " " << v << endl;
#endif
  if (toposort(-1) == a && toposort(+1) == b) {
    cout << "Yes" << endl;
    for (int i = 1; i <= n; i++) {
      auto bg = begin(g[i]), ed = end(g[i]);
      sort(bg, ed), g[i].erase(unique(bg, ed), ed);
      m += (int)g[i].size();
    }
    cout << m << endl;
    for (int i = 1; i <= n; i++) for (int v : g[i]) cout << i << " " << v << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}