QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#203135#6315. 填数游戏zlxFTH100 ✓1706ms305712kbC++145.0kb2023-10-06 15:41:342023-10-06 15:41:35

Judging History

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

  • [2023-10-06 15:41:35]
  • 评测
  • 测评结果：100
  • 用时：1706ms
  • 内存：305712kb
查看
  • [2023-10-06 15:41:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

struct DSU {
  vector<int> fa, siz;
  DSU(int n = 0) : fa(n), siz(n, 1) {
    iota(fa.begin(), fa.end(), 0);
  }
  int find(int u) {
    while (u != fa[u]) {
      u = fa[u] = fa[fa[u]];
    }
    return u;
  }
  bool merge(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) {
      return false;
    }
    fa[u] = v;
    siz[v] += siz[u];
    return true;
  }
};

const int N = 1e6 + 5;
int lim, mn[N << 2], tag[N << 2];
#define ls (2 * i)
#define rs (2 * i + 1)
#define mid ((l + r) / 2)
#define lp ls, l, mid
#define rp rs, mid, r
void pn(int i, int v) {
  mn[i] += v;
  tag[i] += v;
}
void down(int i) {
  if (tag[i]) {
    pn(ls, tag[i]);
    pn(rs, tag[i]);
    tag[i] = 0;
  }
}
void mdf(int ql, int qr, int v, int i = 1, int l = 0, int r = lim) {
  if (ql >= r || qr <= l) return;
  if (ql <= l && qr >= r) {
    pn(i, v);
    return;
  }
  down(i);
  mdf(ql, qr, v, lp);
  mdf(ql, qr, v, rp);
  mn[i] = min(mn[ls], mn[rs]);
}
int qry(int ql, int qr, int i = 1, int l = 0, int r = lim) {
  if (ql >= r || qr <= l) return 1e9;
  if (ql <= l && qr >= r) {
    return mn[i];
  }
  down(i);
  return min(qry(ql, qr, lp), qry(ql, qr, rp));
}
#undef mid

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> a(n), b(n), g(n);
  for (int i = 0, k, x; i < n; i++) {
    cin >> k;
    while (k--) {
      cin >> x;
      a[i].push_back(--x);
    }
  }
  DSU d(m);
  for (int i = 0, k, x; i < n; i++) {
    cin >> k;
    while (k--) {
      cin >> x;
      b[i].push_back(--x);
    }
    if (b[i].size() == 2) {
      d.merge(b[i][0], b[i][1]);
    }
    g[i].resize(b[i].size());
    for (int j = 0; j < g[i].size(); j++) {
      for (auto &y : a[i]) {
        if (y == b[i][j]) g[i][j] = 1;
      }
    }
  }
  vector<int> c(m), dg(m);
  vector<vector<pair<int, int>>> adj(m);
  for (int i = 0; i < n; i++) {
    int u = b[i][0];
    int v = b[i].size() == 1 ? u : b[i][1];
    c[d.find(u)]++;
    dg[u]++, dg[v]++;
    adj[u].push_back({v, i});
    if (u != v) adj[v].push_back({u, i});
  }
  int ans = 0;

  vector<int> is(n, 1), vis(m), got(m), ad(n);
  auto circle = [&](int s) {
    vector<int> ed, nd;
    queue<int> q;
    auto dfs = [&](auto self, int u)->void {
      got[u] = 1;
      for (auto [v, id] : adj[u]) {
        if (!ad[id]) {
          ad[id] = 1;
          ed.push_back(id);
        }
        if (!got[v])
          self(self, v);
      }
      if (dg[u] == 1) {
        q.push(u);
      }
      nd.push_back(u);
    };
    dfs(dfs, s);
    
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (auto [v, id] : adj[u]) if (dg[v] > 1) {
        ans += g[id][v == b[id][0]];
        is[id] = 0;
        if (--dg[v] == 1) {
          q.push(v);
        }
      }
    }

    int res0 = 0, res1 = 0, cnt = 0;
    for (auto u : nd) if (dg[u] > 1) {
      s = u;
    }
    auto pdfs = [&](auto self, int u)->void {
      for (auto [v, id] : adj[u]) if (!vis[id] && dg[v] > 1) {
        vis[id] = 1;
        if (u == v) ans += g[id][0];
        else if (g[id][0] && g[id][1]) cnt++;
        else if (g[id][u == b[id][0]]) res0++;
        else if (g[id][v == b[id][0]]) res1++;
        self(self, v);
      }
    };
    pdfs(pdfs, s);
    if (res0 > res1) swap(res0, res1);
    ans += min((res0 + res1 + cnt) / 2, res0 + cnt);
  };

  vector<int> dfn(m), siz(m);
  auto tree = [&](int s) {
    if (d.siz[s] == 1) return;
    lim = d.siz[s];
    fill(mn, mn + 4 * lim + 5, 0);
    fill(tag, tag + 4 * lim + 5, 0);

    int ti = 0;
    auto dfs = [&](auto self, int u, int fa)->void {
      dfn[u] = ti++;
      siz[u] = 1;
      for (auto [v, id] : adj[u]) if (v != fa) {
        self(self, v, u);
        siz[u] += siz[v];
      }
    };
    dfs(dfs, s, -1);

    int all = 0;
    auto pdfs = [&](auto self, int u, int fa)->void {
      for (auto [v, id] : adj[u]) if (v != fa) {
        self(self, v, u);
        if (g[id][u == b[id][0]]) {
          all += 1;
          mdf(dfn[v], dfn[v] + siz[v], -1);
        } else if (g[id][v == b[id][0]]) {
          mdf(dfn[v], dfn[v] + siz[v], 1);
        }
      }
    };
    pdfs(pdfs, s, -1);

    int res = 0;
    auto rdfs = [&](auto self, int u, int fa)->void {
      res = max(res, mn[1] + all);
      for (auto [v, id] : adj[u]) if (v != fa) {
        if (g[id][0] && g[id][1]) {
          all -= 1;
          mdf(dfn[v], dfn[v] + siz[v], 2);
        }
        self(self, v, u);
        if (g[id][0] && g[id][1]) {
          all += 1;
          mdf(dfn[v], dfn[v] + siz[v], -2);
        }
      }
    };
    rdfs(rdfs, s, -1);
    ans += res;
  };

  for (int i = 0; i < m; i++) if (d.find(i) == i) {
    if (d.siz[i] < c[i]) {
      cout << -1 << "\n";
      return;
    }
    d.siz[i] == c[i] ? circle(i) : tree(i);
  }
  cout << ans << "\n";
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 4
Accepted
time: 1ms
memory: 5728kb

input:

20
9 10
2 5 2
2 4 3
1 3
2 4 10
2 1 7
2 1 2
2 5 3
1 6
2 2 7
2 5 4
2 4 3
2 3 9
2 10 4
2 3 1
2 1 2
2 8 7
2 2 6
2 2 7
9 10
2 2 5
2 2 8
2 7 2
2 4 7
2 6 7
2 10 9
2 9 3
2 5 7
2 1 5
2 2 1
2 8 7
2 7 10
2 4 3
2 6 5
2 9 8
2 2 3
2 6 7
2 5 4
9 10
2 2 7
2 4 10
2 5 6
2 2 6
2 9 8
2 7 5
2 3 6
2 6 3
2 7 6
2 7 8
2 5 4...

output:

4
0
3
1
1
1
8
-1
9
2
5
3
3
5
3
4
3
3
1
4

result:

ok 20 numbers

Test #2:

score: 4
Accepted
time: 1ms
memory: 5664kb

input:

20
9 10
2 4 7
2 6 10
2 9 3
2 5 6
2 7 6
2 3 2
2 4 6
2 8 1
2 3 8
2 8 7
2 10 6
2 3 4
2 5 6
2 6 7
2 1 2
2 4 5
2 8 9
2 3 2
10 10
2 2 1
2 3 7
2 6 10
2 3 4
2 7 4
2 3 4
1 5
2 8 3
2 1 4
2 6 9
2 2 1
2 2 3
2 2 6
2 4 5
2 7 4
2 4 3
2 6 5
2 10 3
2 8 4
2 9 2
10 10
2 9 8
2 7 3
2 1 2
2 10 5
1 6
2 3 2
2 4 10
2 9 1
2 ...

output:

3
5
9
4
3
3
-1
4
5
2
3
2
0
4
3
6
1
5
2
2

result:

ok 20 numbers

Test #3:

score: 4
Accepted
time: 1ms
memory: 5736kb

input:

20
10 10
1 5
2 3 6
2 4 3
2 2 9
2 1 2
2 4 10
2 4 6
2 7 8
2 2 4
2 3 2
2 5 6
2 2 6
2 3 4
2 2 9
2 1 2
2 10 4
2 4 7
2 8 7
2 5 4
2 2 3
9 10
2 5 8
1 2
2 2 6
2 10 3
1 4
2 9 8
1 10
2 7 8
2 5 3
2 7 8
2 1 2
2 6 5
2 2 3
2 4 3
2 8 9
2 5 10
2 7 6
2 5 4
9 10
2 9 5
2 10 2
2 1 9
2 1 8
2 5 10
1 8
1 4
2 4 6
2 1 10
2 1...

output:

6
1
4
4
-1
3
4
3
3
6
4
1
3
9
3
6
3
4
3
0

result:

ok 20 numbers

Test #4:

score: 4
Accepted
time: 0ms
memory: 5676kb

input:

20
9 10
2 2 4
2 6 3
1 2
2 10 7
1 4
2 1 2
1 4
1 6
2 9 4
2 4 2
2 2 3
2 1 10
2 8 7
2 4 7
2 1 2
2 5 4
2 6 2
2 4 9
9 10
2 5 4
2 6 8
2 4 2
2 4 3
2 5 6
2 2 3
2 7 6
2 3 8
2 9 7
2 5 4
2 8 9
2 1 2
2 4 3
2 6 5
2 3 10
2 7 6
2 3 2
2 8 7
9 10
2 4 3
2 9 6
2 2 7
2 5 9
1 8
1 3
2 9 5
2 7 3
1 4
2 10 9
2 6 5
2 2 1
2 5 ...

output:

3
2
0
3
9
3
0
3
4
4
3
6
3
2
3
8
2
-1
3
3

result:

ok 20 numbers

Test #5:

score: 4
Accepted
time: 1ms
memory: 5664kb

input:

20
10 10
2 7 3
2 6 2
1 3
2 1 4
2 3 4
1 1
2 5 4
2 1 8
1 4
2 4 8
2 7 6
2 3 2
2 8 3
2 10 4
2 5 4
2 6 1
2 5 6
2 1 2
2 9 4
2 4 3
10 10
2 2 1
1 4
2 10 3
2 2 4
1 6
2 5 9
2 6 9
1 2
2 3 8
1 2
2 2 10
2 8 4
2 4 3
2 1 2
2 6 5
2 5 4
2 9 6
2 3 2
2 7 3
2 1 2
9 10
2 9 3
1 6
2 2 1
2 9 4
1 4
2 8 1
2 8 6
1 5
1 7
2 3 2...

output:

3
4
1
3
3
-1
3
2
6
2
2
4
3
3
5
4
7
1
3
2

result:

ok 20 numbers

Test #6:

score: 4
Accepted
time: 6ms
memory: 5808kb

input:

1000
10 10
2 1 8
2 8 3
2 3 4
2 2 1
2 4 7
2 7 4
2 9 6
1 5
1 8
2 2 6
2 7 3
2 6 7
2 10 9
2 8 3
2 9 1
2 10 6
2 3 10
2 7 4
2 5 6
2 3 8
9 10
2 8 4
1 3
1 9
2 3 7
2 6 2
2 4 3
2 3 7
2 1 4
2 1 7
2 5 2
2 5 4
2 5 8
2 10 5
2 8 9
2 5 6
1 10
2 8 7
1 10
39 40
2 3 40
2 26 17
2 21 27
2 5 9
1 24
2 19 6
2 25 18
2 18 29...

output:

-1
-1
-1
-1
-1
-1
0
0
0
-1
-1
0
-1
0
0
0
0
-1
0
0
-1
-1
-1
-1
-1
-1
-1
-1
0
0
-1
-1
-1
0
0
-1
-1
-1
0
0
0
-1
-1
-1
0
0
0
-1
0
-1
0
0
0
0
0
0
-1
0
-1
0
0
-1
-1
0
0
-1
0
0
-1
0
0
0
-1
0
-1
0
0
-1
-1
-1
0
0
0
0
-1
-1
0
-1
-1
-1
-1
0
0
0
-1
0
0
-1
-1
-1
-1
0
-1
0
-1
0
0
0
0
-1
0
0
-1
0
0
0
-1
-1
0
0
-1
...

result:

ok 1000 numbers

Test #7:

score: 4
Accepted
time: 6ms
memory: 3700kb

input:

1000
10 10
2 2 6
1 2
1 3
1 5
2 9 10
2 6 7
1 7
2 4 8
2 9 4
1 10
2 2 1
2 3 2
2 4 3
2 5 4
2 6 5
2 7 6
2 7 8
2 9 8
2 10 9
2 10 1
9 10
2 1 2
2 2 3
1 7
1 4
2 1 6
2 7 6
2 7 3
2 4 9
2 1 9
2 2 1
2 3 2
2 4 3
2 4 5
2 6 5
2 6 7
2 8 7
2 9 8
2 9 1
9 10
2 1 7
1 10
2 3 6
2 9 5
2 5 4
1 6
2 8 7
2 8 9
2 9 8
2 1 2
2 2 ...

output:

3
4
3
4
2
3
4
3
2
4
3
3
3
5
2
3
5
5
5
3
2
3
3
2
13
4
4
3
1
3
2
2
3
4
4
3
4
2
4
3
4
4
2
3
4
4
3
1
1
3
3
1
4
4
24
4
4
2
4
3
2
2
2
1
3
4
4
2
1
5
4
3
4
0
4
4
4
3
2
4
4
4
4
5
1
3
4
3
3
2
3
2
3
3
4
4
3
1
3
4
3
2
3
3
1
2
35
1
4
3
3
4
4
2
3
3
3
2
4
3
4
3
3
1
3
2
2
17
3
4
2
3
4
11
4
4
3
4
2
9
2
5
2
2
3
3
4
3...

result:

ok 1000 numbers

Test #8:

score: 4
Accepted
time: 4ms
memory: 5812kb

input:

1000
1 10
1 7
1 7
2 10
1 8
1 3
1 8
1 3
2 10
1 1
1 9
1 1
1 9
5 10
1 7
1 6
1 4
1 3
1 10
1 7
1 6
1 4
1 3
1 10
29 40
1 9
1 15
1 29
1 20
1 8
1 30
1 27
1 7
1 24
1 8
1 23
1 17
1 10
1 28
1 26
1 19
1 15
1 33
1 16
1 14
1 10
1 30
1 20
1 40
1 22
1 10
1 31
1 38
1 5
2 28 9
2 15 6
2 39 29
2 20 31
2 8 38
2 30 25
1 ...

output:

1
2
2
5
8
3
3
4
5
1
7
3
5
2
1
2
3
2
4
1
2
14
4
2
3
4
1
3
4
3
3
4
3
4
3
4
4
4
11
10
3
3
3
2
3
4
5
3
2
3
3
3
5
3
10
4
4
2
7
12
3
3
3
3
1
4
2
2
5
4
4
3
3
6
4
2
5
4
3
4
5
3
4
4
3
32
3
2
4
3
4
7
2
4
6
4
3
3
3
4
3
1
3
4
2
4
3
5
4
3
4
3
3
4
2
2
2
5
2
4
3
3
3
2
2
3
3
4
3
1
4
5
3
4
2
3
2
3
4
2
4
13
3
4
3
3
3...

result:

ok 1000 numbers

Test #9:

score: 4
Accepted
time: 5ms
memory: 5780kb

input:

1000
5 10
1 7
2 9 8
2 1 4
1 3
2 2 9
1 7
2 9 8
2 1 4
1 3
2 2 9
6 10
2 3 6
2 2 5
2 6 3
2 2 5
2 8 9
1 4
2 6 3
2 5 2
2 6 3
2 5 2
2 9 8
1 4
8 10
1 8
2 5 6
2 5 6
2 3 8
2 9 7
2 7 9
1 4
1 10
1 8
2 6 5
2 6 5
2 8 3
2 7 9
2 7 9
1 4
1 10
6 10
1 9
1 4
1 3
2 7 1
1 5
2 1 6
1 9
1 4
1 3
2 7 1
1 5
2 1 6
6 10
2 6 1
2 ...

output:

3
3
6
5
3
2
8
4
4
48
4
7
5
2
3
3
1
4
2
20
4
6
22
3
5
3
6
3
2
6
3
6
8
15
7
5
7
6
3
4
5
5
4
3
3
7
7
2
55
3
1
3
5
4
5
4
4
4
7
5
8
7
6
5
6
6
2
4
4
4
5
7
6
3
5
5
6
3
5
7
5
6
4
6
6
5
3
2
6
4
4
6
3
22
4
7
5
3
7
5
5
3
56
3
1
5
7
7
5
4
4
3
3
8
4
3
1
3
-1
5
45
4
4
3
4
5
6
7
4
6
5
5
5
4
6
19
16
6
4
2
2
6
17
3
...

result:

ok 1000 numbers

Test #10:

score: 4
Accepted
time: 4ms
memory: 5840kb

input:

1000
7 10
2 6 9
2 7 1
2 3 2
2 3 10
2 4 10
1 8
2 2 6
1 9
1 7
2 2 3
1 10
2 2 4
1 8
1 6
6 10
2 2 7
2 10 4
1 9
1 10
2 10 6
1 5
1 7
1 4
1 9
1 10
1 6
1 5
6 10
1 4
2 9 2
2 6 5
1 7
2 6 7
1 10
1 4
1 9
1 5
1 7
1 6
1 10
6 10
2 2 8
1 7
2 3 6
2 6 4
2 10 4
1 8
2 4 2
1 7
2 2 3
1 6
1 10
1 8
6 10
1 5
2 1 2
1 7
2 2 6...

output:

6
6
6
4
5
6
5
5
6
4
4
5
4
19
4
5
3
5
5
5
6
20
5
6
3
6
3
5
4
4
4
4
6
5
34
3
4
5
4
7
6
7
4
3
6
4
6
4
5
4
5
4
7
4
5
6
5
4
4
4
5
6
5
14
5
5
6
5
4
5
7
5
3
5
14
6
5
15
6
5
4
5
5
5
5
4
3
3
4
6
4
5
6
4
6
13
4
4
6
3
5
4
4
4
5
3
4
3
4
3
15
4
5
4
4
5
3
3
5
5
5
4
7
6
5
5
4
7
5
5
5
6
5
3
4
71
6
4
3
6
5
5
6
5
5
3...

result:

ok 1000 numbers

Test #11:

score: 4
Accepted
time: 4ms
memory: 5744kb

input:

1000
5 10
1 1
2 6 5
1 5
2 9 7
1 8
2 1 2
1 6
2 1 3
1 7
1 8
7 10
1 8
2 4 7
2 8 5
1 10
2 2 9
1 7
1 6
1 8
1 4
1 5
1 10
1 9
1 7
1 6
5 10
2 2 5
2 4 9
2 9 8
2 9 10
1 6
1 5
1 4
1 8
1 9
1 6
6 10
2 2 5
2 10 7
1 4
2 6 4
1 8
2 5 7
1 5
1 10
1 4
1 6
1 8
1 7
5 10
2 7 8
2 3 1
1 6
1 1
1 8
1 7
2 1 3
1 6
2 1 2
1 8
5 1...

output:

3
7
5
6
3
4
6
5
5
5
7
4
5
36
6
3
5
6
5
4
3
4
5
6
7
4
5
5
4
4
5
4
5
5
7
3
3
6
4
4
6
9
6
4
4
5
6
4
5
6
4
6
5
4
3
4
14
5
4
5
4
5
4
6
5
4
3
5
5
3
5
5
5
5
7
5
6
4
5
5
13
5
5
9
5
5
3
4
4
4
5
7
5
5
3
6
5
4
4
4
5
5
7
-1
4
6
6
5
5
4
4
5
6
4
6
4
6
4
3
9
5
4
4
4
5
6
12
4
4
4
5
5
5
4
5
7
17
6
4
6
3
5
6
19
5
16
...

result:

ok 1000 numbers

Test #12:

score: 4
Accepted
time: 67ms
memory: 6552kb

input:

1000
89 100
2 7 10
2 44 79
2 90 72
2 81 82
2 97 98
1 26
2 12 11
2 19 22
2 75 76
2 87 57
2 93 20
2 14 15
1 18
2 52 56
2 63 65
1 52
2 19 69
2 17 30
1 80
2 87 88
2 32 79
2 65 57
2 10 99
2 74 71
1 90
2 61 62
2 61 40
2 15 59
2 78 53
1 71
2 82 36
2 29 8
2 17 18
2 92 67
2 81 63
2 4 5
2 51 54
2 14 13
1 62
2...

output:

38
39
38
40
36
37
35
33
34
37
33
170
32
34
39
40
41
32
42
35
32
33
26
38
32
44
39
29
167
144
32
38
34
34
41
156
40
37
42
36
31
-1
43
182
40
39
175
32
39
33
36
30
33
-1
42
44
38
26
32
43
44
37
31
40
37
33
39
32
31
162
44
36
37
35
40
34
38
36
33
35
29
32
39
175
29
34
36
33
43
31
35
33
32
39
36
33
45
3...

result:

ok 1000 numbers

Test #13:

score: 4
Accepted
time: 72ms
memory: 6492kb

input:

1000
94 100
2 52 4
1 59
1 47
1 59
2 42 94
2 12 13
2 71 87
2 60 59
2 57 47
2 94 70
1 64
2 12 27
2 77 94
2 50 35
1 5
2 70 58
2 64 56
2 67 68
2 21 29
1 26
2 100 73
2 92 93
1 73
2 71 72
2 38 36
2 50 20
1 74
2 47 87
1 4
1 76
2 92 99
2 82 64
2 48 49
2 15 14
2 38 69
1 51
2 55 42
1 68
1 45
2 21 16
1 30
2 91...

output:

41
27
39
33
35
25
31
34
33
36
41
32
44
46
38
37
44
32
37
160
32
40
441
38
38
44
31
39
31
45
37
46
45
41
173
35
35
36
36
36
30
39
35
41
39
32
449
41
44
34
35
36
35
33
30
37
33
32
42
34
34
31
32
36
34
34
39
424
43
31
34
30
32
32
39
35
39
33
37
29
36
34
33
162
30
37
36
34
-1
44
33
37
37
163
41
46
37
15...

result:

ok 1000 numbers

Test #14:

score: 4
Accepted
time: 171ms
memory: 52328kb

input:

1000
88 90
2 59 42
1 45
2 68 83
2 36 2
2 89 70
1 7
1 8
2 67 55
2 81 47
2 76 36
1 68
2 86 27
1 8
1 12
1 4
2 64 21
2 11 1
2 6 69
2 39 58
2 39 40
1 3
2 39 76
1 62
2 43 69
1 53
1 79
2 78 65
2 85 1
1 75
2 47 87
2 26 41
2 17 38
1 2
2 25 41
2 86 71
1 37
2 31 80
1 14
2 47 12
2 66 78
2 28 83
1 57
1 69
2 53 6...

output:

-1
0
-1
-1
-1
0
-1
-1
-1
-1
-1
0
0
0
-1
0
0
-1
-1
-1
-1
-1
-1
0
0
0
0
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
0
0
-1
-1
-1
-1
-1
-1
-1
-1
0
0
0
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
0
-1
-1
0
0
-1
-1
-1
-1
-1
0
-1
-1
0
0
-1
-1
-1
0
0
-1
-1
-1
-1
-1
-...

result:

ok 1000 numbers

Test #15:

score: 4
Accepted
time: 148ms
memory: 58312kb

input:

1000
86 90
1 2
2 2 79
2 4 89
2 55 4
2 12 6
2 6 70
2 7 9
2 8 39
2 30 10
2 10 35
2 70 8
2 12 13
1 13
2 14 35
2 15 21
2 42 16
1 28
1 18
1 19
2 75 20
2 21 5
2 81 22
2 55 23
2 24 19
1 25
1 62
1 27
1 28
2 59 29
2 31 30
2 32 31
1 32
1 33
1 35
1 35
2 36 70
2 85 29
2 39 38
1 39
1 40
2 18 41
1 42
2 84 44
2 44...

output:

22
25
37
40
30
30
36
26
23
36
29
29
17
27
33
22
37
20
36
26
35
29
40
26
21
40
26
19
33
27
24
37
20
21
29
23
23
22
36
36
34
27
22
39
38
40
39
20
22
18
35
27
36
25
32
21
40
36
21
36
25
19
27
38
37
27
17
25
39
23
25
38
26
26
31
37
27
37
36
17
23
21
23
28
37
27
20
38
29
22
21
20
23
41
22
38
24
22
26
26
...

result:

ok 1000 numbers

Test #16:

score: 4
Accepted
time: 133ms
memory: 59104kb

input:

1000
90 90
2 25 2
2 27 3
2 85 4
2 5 4
2 19 6
2 6 7
2 50 7
2 9 69
1 10
1 11
1 11
1 13
2 14 16
1 15
1 16
2 88 16
1 26
2 76 19
2 19 20
1 20
1 22
2 53 22
2 26 24
1 25
2 25 26
2 8 61
1 23
2 66 29
2 21 30
1 31
2 32 1
2 67 32
2 56 34
1 34
2 36 35
1 36
2 37 40
2 20 39
1 40
2 65 41
2 64 42
2 74 54
2 24 44
2 ...

output:

21
37
29
38
19
27
36
38
23
21
23
38
37
24
19
23
32
27
37
39
18
25
30
28
25
28
24
29
21
32
18
26
34
27
39
29
31
21
21
29
22
31
37
19
27
25
20
36
27
22
37
26
30
24
37
27
35
36
41
27
39
40
16
19
26
24
21
21
37
36
256
36
37
21
37
15
24
24
23
19
39
29
27
38
26
28
38
26
26
40
38
38
19
27
28
38
21
28
20
38...

result:

ok 1000 numbers

Test #17:

score: 4
Accepted
time: 207ms
memory: 48156kb

input:

1000
76 90
1 3
1 83
1 67
1 28
1 17
1 63
1 16
1 13
1 27
1 75
1 12
1 85
1 19
1 40
1 30
1 32
1 58
1 20
1 83
1 72
1 50
1 11
1 53
1 39
1 3
1 58
1 71
1 31
1 6
1 35
1 20
1 62
1 43
1 63
1 32
1 51
1 55
1 73
1 33
1 8
1 34
1 21
1 55
1 44
1 50
1 81
1 84
1 88
1 65
1 53
1 28
1 40
1 14
1 77
1 4
1 87
1 13
1 89
1 11...

output:

28
25
29
36
29
35
31
38
38
31
24
24
25
36
30
36
28
32
31
27
22
31
24
23
29
31
32
29
28
26
32
24
33
31
27
400
25
29
28
30
30
28
29
36
37
28
26
33
31
31
33
32
25
30
34
30
27
26
22
27
39
26
32
37
32
25
22
28
29
26
25
41
34
36
27
31
29
26
29
31
33
29
33
31
27
31
27
36
32
34
29
30
35
30
25
38
33
32
36
27...

result:

ok 1000 numbers

Test #18:

score: 4
Accepted
time: 225ms
memory: 51512kb

input:

1000
83 90
1 34
1 30
1 86
1 13
1 82
1 25
1 83
1 45
1 26
1 12
1 49
1 56
1 73
1 40
1 35
1 34
1 5
1 80
1 69
1 81
1 25
1 67
1 20
1 54
1 62
1 83
1 21
1 35
1 52
1 67
1 47
1 69
1 11
1 85
1 31
1 33
1 51
1 4
1 9
1 63
1 18
1 41
1 63
1 11
1 48
1 43
1 65
1 53
1 61
1 2
1 5
1 76
1 75
1 77
1 64
1 78
1 14
1 72
1 8
...

output:

32
28
29
29
23
38
26
32
31
37
28
31
32
32
27
29
28
29
23
30
36
34
30
26
25
27
25
27
27
32
35
25
24
24
27
25
35
32
28
24
33
31
31
36
31
40
29
27
33
26
-1
33
32
27
28
27
27
30
29
29
30
28
32
31
32
25
28
30
39
29
31
31
28
30
32
30
30
28
29
27
33
29
27
31
29
23
24
32
27
31
38
30
32
34
25
33
24
27
28
29
...

result:

ok 1000 numbers

Test #19:

score: 4
Accepted
time: 181ms
memory: 37348kb

input:

1000
62 90
1 59
2 46 10
2 85 2
2 79 41
2 34 88
2 49 7
2 66 19
2 77 75
2 26 86
2 68 13
2 71 85
2 11 29
2 65 74
2 80 19
2 87 48
2 17 27
2 21 46
1 44
2 30 27
1 20
2 86 58
2 85 40
2 40 36
2 1 27
2 74 44
1 72
2 14 12
2 18 29
2 39 33
2 66 19
2 90 60
2 47 62
2 52 90
2 12 80
2 68 75
2 51 29
2 1 57
1 61
2 43...

output:

48
50
50
41
42
39
45
48
44
45
48
49
38
50
43
48
46
39
47
46
41
47
45
47
43
40
36
45
50
46
38
52
47
47
44
45
41
36
48
42
39
44
47
44
49
48
42
48
50
46
48
42
46
42
41
44
41
-1
42
44
47
45
46
51
44
44
53
53
41
42
46
35
43
48
51
48
49
49
46
42
44
47
80116
47
47
50
39
39
44
43
42
52
547
42
43
45
47
43
42...

result:

ok 1000 numbers

Test #20:

score: 4
Accepted
time: 175ms
memory: 39016kb

input:

1000
65 90
2 33 90
2 61 28
2 39 71
2 58 78
2 9 41
2 70 84
2 20 64
2 26 3
2 73 57
2 21 4
2 89 88
2 69 85
2 82 55
2 20 39
2 5 27
2 9 42
2 64 25
2 85 81
2 26 3
1 15
2 87 60
2 86 1
2 10 22
2 66 28
2 66 12
2 19 14
2 8 33
2 84 70
2 11 39
1 16
2 75 37
2 47 39
1 51
2 78 57
2 19 18
2 77 74
2 59 15
2 76 65
2 ...

output:

48
39
44
43
44
43
54
43
45
48
53
50
46
41
46
43
43
46
50
44
47
38
48
42
38
49
40
47
41
50
535
44
47
42
45
50
47
51
42
44
39
49
47
53
48
43
49
43
46
43
51
41
47
49
39
43
46
50
39
43
51
544
53
46
50
44
40
42
37
49
-1
48
50
43
40
48
45
44
44
38
48
51
46
46
49
50
50
40
46
43
53
44
45
43
51
40
47
42
51
4...

result:

ok 1000 numbers

Test #21:

score: 4
Accepted
time: 225ms
memory: 48768kb

input:

1000
76 90
2 15 3
2 61 68
2 35 15
2 67 86
1 36
1 40
2 13 12
2 30 37
2 14 64
2 29 68
2 15 14
2 17 25
2 11 12
2 79 13
2 62 7
2 35 1
2 42 71
2 33 38
1 85
2 47 17
2 39 37
2 60 6
1 77
1 57
2 39 29
1 71
2 30 47
2 30 33
2 64 79
2 42 77
2 45 38
2 33 1
2 75 76
2 18 26
1 18
2 57 56
2 19 55
2 7 81
2 53 19
2 56...

output:

34
33
39
30
38
33
32
35
28
30
36
27
35
31
37
32
31
32
35
30
39
24
29
30
39
36
33
38
34
38
32
34
30
25
33
29
33
32
31
31
32
32
27
29
30
37
36
35
36
32
65796
39
33
33
24
29
29
24
28
38
24
28
34
31
27
29
-1
28
31
34
37
29
31
23
31
31
31
34
35
36
36
29
33
31
38
38
38
35
26
28
36
30
38
33
28
29
31
26
34
...

result:

ok 1000 numbers

Test #22:

score: 4
Accepted
time: 225ms
memory: 51032kb

input:

1000
80 90
2 48 50
2 20 23
2 82 8
1 4
1 40
2 69 59
2 13 67
2 6 86
2 3 74
2 9 38
1 9
1 79
1 18
2 15 14
1 31
2 77 21
2 33 72
2 56 39
2 32 33
2 90 89
2 86 83
2 90 13
2 34 26
2 23 68
1 50
2 65 83
1 77
2 79 69
2 25 26
2 44 43
2 74 84
2 13 12
1 62
1 71
2 26 70
2 2 83
2 7 20
2 23 1
2 11 12
2 78 7
1 58
1 65...

output:

33
36
30
41
26
26
32
27
26
29
34
37
32
30
27
32
35
33
37
30
25
36
30
33
33
38
30
37
29
31
32
29
26
35
29
28
34
31
28
28
34
27
37
34
33
30
35
38
35
28
39
27
35
32
34
36
25
22
26
26
28
31
35
32
33
26
35
32
34
29
31
34
30
31
36
29
25
34
43
32
32
33
39
27
32
24
31
28
29
37
29
35
28
33
30
34
35
32
32
31
...

result:

ok 1000 numbers

Test #23:

score: 4
Accepted
time: 1706ms
memory: 304004kb

input:

1000
82 90
2 36 58
2 64 41
2 1 12
2 6 90
2 50 15
2 30 27
2 42 87
2 89 33
2 47 28
1 70
1 17
1 20
2 33 62
2 31 7
2 4 69
2 83 37
2 55 36
2 35 32
2 29 11
1 57
2 53 52
2 9 53
2 88 66
1 21
1 22
2 28 39
2 11 12
1 5
2 78 56
2 59 57
2 63 8
2 85 62
2 84 16
2 48 49
2 7 61
2 3 9
1 4
1 50
1 80
2 62 43
2 77 50
2 ...

output:

32
34
34
34
29
38
32
39
39
34
23
33
28
37
33
41
36
35
35
25
34
29
30
24
27
38
36
40
31
29
35
30
38
29
36
31
29
35
39
35
29
29
27
26
32
30
47
30
31
42
37
33
26
35
27
29
38
39
33
27
31
35
29
39
35
36
-1
34
36
33
33
-1
38
28
29
33
27
27
39
31
32
36
32
30
29
32
26
35
37
24
33
35
35
29
34
27
31
28
30
30
...

result:

ok 1000 numbers

Test #24:

score: 4
Accepted
time: 1631ms
memory: 297952kb

input:

1000
83 90
2 71 72
2 6 16
2 78 3
2 24 25
2 39 65
2 19 9
2 10 14
1 30
2 86 65
2 17 18
1 47
2 69 68
1 7
2 64 7
2 31 68
2 90 89
2 85 4
2 22 79
2 12 62
2 56 66
1 83
1 88
2 43 45
2 50 20
2 15 14
2 38 59
1 32
1 80
2 33 6
1 61
2 15 41
2 47 20
2 78 52
2 1 13
1 18
2 6 63
2 70 62
2 25 27
1 74
2 8 2
2 65 41
2 ...

output:

37
29
31
31
34
32
33
35
32
31
30
27
32
36
33
27
29
28
35
33
27
37
30
33
27
29
27
33
33
36
37
24
34
33
29
29
36
41
34
34
25
35
33
24
21
36
33
33
32
30
35
32
36
34
30
31
38
30
27
34
30
33
29
31
32
37
37
31
30
24
26
33
33
28
31
29
35
39
31
26
34
33
29
37
35
29
29
34
33
33
29
34
32
27
35
34
29
35
25
32
...

result:

ok 1000 numbers

Test #25:

score: 4
Accepted
time: 1691ms
memory: 305712kb

input:

1000
80 90
2 66 52
2 74 17
2 42 71
2 59 58
2 86 21
1 81
2 25 63
1 52
1 1
1 25
2 2 22
1 89
1 39
1 28
2 78 85
2 67 76
1 85
2 30 31
2 12 13
2 25 38
1 33
2 38 71
1 9
2 62 61
1 16
1 54
2 52 66
2 5 15
2 14 13
2 69 3
2 70 66
2 37 25
2 21 27
2 34 6
2 44 85
2 12 33
1 75
2 51 53
2 4 45
2 39 82
1 26
1 15
2 46 ...

output:

38
31
31
25
32
398
36
34
34
31
33
38
36
32
33
37
26
37
30
38
32
34
39
30
36
31
28
30
40
38
28
31
41
34
36
31
35
36
30
33
33
39
39
30
30
29
31
31
31
34
34
38
34
39
33
39
35
40
30
35
29
33
30
34
37
40
38
34
31
34
37
34
31
41
37
31
34
37
32
36
34
37
37
37
33
26
39
37
29
28
39
30
37
31
33
32
30
37
31
35...

result:

ok 1000 numbers

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

伺服器時間: 2024-12-02 17:56:17 | 開源專案