QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#530184#9221. Missing Boundariesucup-team896#WA 74ms20184kbC++203.2kb2024-08-24 15:15:592024-08-24 15:15:59

Judging History

你现在查看的是最新测评结果

  • [2024-08-24 15:15:59]
  • 评测
  • 测评结果:WA
  • 用时:74ms
  • 内存:20184kb
  • [2024-08-24 15:15:59]
  • 提交

answer

#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 400010;

int n, m, c[maxn], fa[maxn], L[maxn], R[maxn], vis[maxn], tot;
pii a[maxn];
vector<pii> vec[maxn];

int find(int x) {
  return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void work() {
  cin >> n >> m;
  rep (i, 1, n) cin >> a[i].fi >> a[i].se;
  rep (i, 1, n) if (a[i].fi != -1) a[i].fi--;
  tot = 0;
  rep (i, 1, n) if (a[i].fi != -1) c[++tot] = a[i].fi;
  rep (i, 1, n) if (a[i].se != -1) c[++tot] = a[i].se;
  c[++tot] = 0, c[++tot] = m;
  sort(c + 1, c + tot + 1), tot = unique(c + 1, c + tot + 1) - c - 1;
  rep (i, 1, n) if (a[i].fi != -1) a[i].fi = lower_bound(c + 1, c + tot + 1, a[i].fi) - c;
  rep (i, 1, n) if (a[i].se != -1) a[i].se = lower_bound(c + 1, c + tot + 1, a[i].se) - c;
  rep (i, 1, tot) fa[i] = i, L[i] = R[i] = 0;
  rep (i, 1, n) if (a[i].fi != -1 && a[i].se != -1) fa[find(a[i].fi)] = find(a[i].se);
  rep (i, 1, tot) vec[i].clear();
  rep (i, 1, n) if (a[i].fi != -1 && a[i].se != -1) vec[find(a[i].fi)].emplace_back(a[i].fi, a[i].se);
  rep (i, 1, n) if (a[i].fi != -1 && a[i].se == -1) L[a[i].fi]++;
  rep (i, n, 1) if (a[i].fi == -1 && a[i].se != -1) R[a[i].se]++;
  int ac = 0;
  rep (i, 1, n) if (a[i].fi == -1 && a[i].se == -1) ac++;
  int rest = m;
  rep (i, 1, tot) if (SZ(vec[i])) {
    sort(ALL(vec[i]));
    rep (j, 0, SZ(vec[i]) - 2) if (vec[i][j].se != vec[i][j + 1].fi) return cout << "NIE\n", void();
    if (SZ(vec[i]) != vec[i].back().se - vec[i][0].fi) return cout << "NIE\n", void();
    rest -= c[vec[i].back().se] - c[vec[i][0].fi];
  }
  rep (i, 1, tot) rest -= L[i] + R[i];
  if (ac > rest) return cout << "NIE\n", void();
  rep (i, 1, tot) vis[i] = 0;
  for (int l = 1, r; l <= tot; l = r + 1) {
    r = l;
    while (r < tot && find(r + 1) == find(l)) r++;
    if (r - l + 1 > 1) {
      rep (i, l, r) vis[i] = 1;
    }
  }
  // rep (i, 1, tot) cerr << vis[i] << " \n"[i == tot];
  for (int l = 1, r; l <= tot; l = r + 1) {
    r = l;
    if (!(l == 1 && !vis[l]) && (l == tot || vis[l + 1])) continue;
    r++;
    while (r < tot && !vis[r]) r++;
    // cerr << l << " " << r << endl;
    while (l <= tot && L[l]) L[l]--, l++;
    while (r >= 1 && R[r]) R[r]--, r--;
    if (l == r) continue;
    if (l > r) return cout << "NIE\n", void();
    int lst = 0;
    for (int i = l + 1; i <= r - 1; i++) {
      if (lst && R[i] && c[i] - c[i - 1] >= 2) R[i]--;
      if (!lst && R[i]) R[i]--;
      else if (!lst) ac--;
      if (L[i]) L[i]--, lst = 1;
      else lst = 0;
    }
    if (!lst) ac--;
  }
  if (ac < 0) return cout << "NIE\n", void();
  rep (i, 1, tot) if (L[i] || R[i]) return cout << "NIE\n", void();
  cout << "TAK\n";
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  int t; cin >> t;
  while (t--) work();
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 11860kb

input:

3
4 51
1 -1
11 50
-1 -1
-1 10
3 2
-1 -1
-1 -1
-1 -1
2 3
1 2
2 3

output:

TAK
NIE
NIE

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 74ms
memory: 20184kb

input:

1
200000 1000000000
490669427 -1
224278942 224287156
821104480 -1
861696576 861702036
807438935 807440055
574078002 574083717
465630141 -1
195378188 -1
-1 13500961
-1 977536179
92893115 -1
-1 661145418
-1 215804863
-1 685338515
544348999 -1
465532902 -1
130346949 -1
-1 526666304
635604584 635605404
...

output:

NIE

result:

wrong answer 1st lines differ - expected: 'TAK', found: 'NIE'