QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#384625#5531. ICCnhuang68590 78ms4308kbC++204.3kb2024-04-10 07:46:222024-04-10 07:46:23

Judging History

你现在查看的是测评时间为 2024-04-10 07:46:23 的历史记录

  • [2024-07-01 04:28:53]
  • 管理员手动重测本题所有提交记录
  • 测评结果:90
  • 用时:81ms
  • 内存:4136kb
  • [2024-04-10 07:46:23]
  • 评测
  • 测评结果:90
  • 用时:78ms
  • 内存:4308kb
  • [2024-04-10 07:46:22]
  • 提交

answer

#include <bits/stdc++.h>

#ifndef LOCAL
#include "icc.h"
#endif

std::vector<std::vector<int>> gr;
std::vector<int> par;
std::vector<int> nodes;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
// std::mt19937 rng(2);
int find(int a) { return par[a] < 0 ? a : par[a] = find(par[a]); }

#ifdef LOCAL
namespace iv {
std::array<std::array<bool, 101>, 101> cc;
int na = -1, nb = -1;
int cnt = 0;
int num = 0;
int n;
} // namespace iv

int query(int a, int b, int *A, int *B) {
  ++iv::cnt;
  for (int ii = 0; ii < a; ++ii) {
    int i = A[ii];
    for (int jj = 0; jj < b; ++jj) {
      int j = B[jj];
      if (iv::cc[i][j]) {
        return true;
      }
    }
  }
  return false;
}
bool connected(int a, int b) {
  if (a == b) {
    return true;
  }
  if (par.empty()) {
    return false;
  }
  a = find(a);
  b = find(b);
  return a == b;
}
void newQuery() {
  while (true) {
    int a, b;
    // a = iv::num + 1;
    // b = iv::num + 2;
    if (iv::num == 0) {
      a = (int)(rng() % iv::n) + 1;
      b = (int)(rng() % iv::n) + 1;
    } else {
      int aa = (int)(rng() % iv::n) + 1;
      if (gr[aa].empty()) {
        continue;
      }
      a = gr[aa][rng() % gr[aa].size()];
      int bb = (int)(rng() % iv::n) + 1;
      if (gr[bb].empty()) {
        continue;
      }
      b = gr[bb][rng() % gr[bb].size()];
    }
    if (!connected(a, b)) {
      if (a > b) {
        std::swap(a, b);
      }
      iv::na = a;
      iv::nb = b;
      iv::cc[a][b] = true;
      iv::cc[b][a] = true;
      return;
    }
  }
}
void setRoad(int a, int b) {
  if (a > b) {
    std::swap(a, b);
  }
  ++iv::num;
  std::cerr << "Query " << iv::num << ":" << std::endl;
  std::cerr << "Your answer is: " << a << ' ' << b << std::endl;
  std::cerr << "The correct answer is: " << iv::na << ' ' << iv::nb
            << std::endl;
  std::cerr << std::endl;
  if (iv::na != a || iv::nb != b) {
    std::cerr << "Wrong Answer" << std::endl;
    std::exit(0);
  }
  if (iv::num < iv::n - 1) {
    newQuery();
  }
}
#endif

bool query(std::vector<int> &a, std::vector<int> &b) {
  if (a.empty() || b.empty()) {
    return false;
  }
  return query((int)a.size(), (int)b.size(), a.data(), b.data());
}
bool queryG(std::vector<int> &ag, std::vector<int> &bg) {
  std::vector<int> a, b;
  for (int i : ag) {
    a.insert(a.end(), gr[i].begin(), gr[i].end());
  }
  for (int i : bg) {
    b.insert(b.end(), gr[i].begin(), gr[i].end());
  }
  return query(a, b);
}
void unite(int a, int b) {
  int aa = a, bb = b;
  a = find(a);
  b = find(b);
  if (par[a] > par[b]) {
    std::swap(a, b);
  }
  gr[a].insert(gr[a].end(), gr[b].begin(), gr[b].end());
  gr[b].clear();
  par[a] += par[b];
  par[b] = a;
  setRoad(aa, bb);
}

const int LG = 7;
void run(int N) {
  const int n = N;
  gr.resize(n + 1);
  for (int i = 1; i <= n; ++i) {
    gr[i].push_back(i);
  }
  par.resize(n + 1, -1);

  for (int i = 0; i < n - 1; ++i) {
    // std::vector<int> a, b;
    std::vector<int> seq(LG);
    std::iota(seq.begin(), seq.end(), 0);
    std::shuffle(seq.begin(), seq.end(), rng);
    std::vector<int> a, b;
    nodes.clear();
    for (int j = 1; j <= n; ++j) {
      if (!gr[j].empty()) {
        nodes.push_back(j);
      }
    }
    for (int j : seq) {
      a.clear();
      b.clear();
      for (int k : nodes) {
        if ((1 << j) & k) {
          a.insert(a.end(), gr[k].begin(), gr[k].end());
        } else {
          b.insert(b.end(), gr[k].begin(), gr[k].end());
        }
      }
      if (query(a, b)) {
        break;
      }
    }

    while ((int)a.size() > 1) {
      std::vector<int> na1(a.begin(), a.begin() + a.size() / 2),
          na2(a.begin() + a.size() / 2, a.end());
      if (query(na1, b)) {
        a = na1;
      } else {
        a = na2;
      }
    }
    while ((int)b.size() > 1) {
      std::vector<int> nb1(b.begin(), b.begin() + b.size() / 2),
          nb2(b.begin() + b.size() / 2, b.end());
      if (query(nb1, a)) {
        b = nb1;
      } else {
        b = nb2;
      }
    }
    unite(a[0], b[0]);
  }
}

#ifdef LOCAL
int main() {
  int n;
  std::cin >> n;
  iv::n = n;
  newQuery();
  run(n);
  std::cerr << "Number of queries used: " << iv::cnt << '\n';
}
#endif

詳細信息

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 4ms
memory: 4212kb

input:

1
1500 3
15

0
2

0.0
2.5

0
3.5

0

1 1

output:

3
Ok! 98 queries used.

result:

points 1.0

Test #2:

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

input:

1
1500 4
15

0
0

0.0
3.5

0
2.5

5

1 1

output:

4
Ok! 100 queries used.

result:

points 1.0

Subtask #2:

score: 11
Accepted

Test #3:

score: 11
Accepted
time: 19ms
memory: 4300kb

input:

1
2500 4
50

0
0

0.0
3.5

0
2.5

5

1 1

output:

4
Ok! 558 queries used.

result:

points 1.0

Test #4:

score: 0
Accepted
time: 25ms
memory: 4172kb

input:

1
2500 4
50

0
1.3

0.0
0.7

0
3.5

15

2 1

output:

4
Ok! 714 queries used.

result:

points 1.0

Test #5:

score: 0
Accepted
time: 21ms
memory: 4300kb

input:

1
2500 3
50

0.05
2.3

0.1
0.7

0
1.5

1.7

2 1

output:

3
Ok! 690 queries used.

result:

points 1.0

Subtask #3:

score: 22
Accepted

Test #6:

score: 22
Accepted
time: 60ms
memory: 4228kb

input:

1
2250 6
100

0.05
2.3

0.1
0.7

0
1.5

1.7

1.1 1

output:

6
Ok! 1402 queries used.

result:

points 1.0

Test #7:

score: 0
Accepted
time: 78ms
memory: 4228kb

input:

1
2250 6
100

0.05
1.5

0.1
1.3

0.01
1.7

0

100 1

output:

6
Ok! 1776 queries used.

result:

points 1.0

Test #8:

score: 0
Accepted
time: 69ms
memory: 4180kb

input:

1
2250 5
100

0.00
2.00

0.00
1.70

0.10
1.30

5

1.15 1

output:

5
Ok! 1571 queries used.

result:

points 1.0

Test #9:

score: 0
Accepted
time: 64ms
memory: 4172kb

input:

1
2250 5
100

0.00
1.00

0.00
2.30

0.00
0.70

0

1.1 1

output:

5
Ok! 1494 queries used.

result:

points 1.0

Subtask #4:

score: 21
Accepted

Test #10:

score: 21
Accepted
time: 65ms
memory: 4308kb

input:

1
2000 5
100

0.01
1.00

0.10
1.70

0.00
1.50

5.0

1.20 1

output:

5
Ok! 1521 queries used.

result:

points 1.0

Test #11:

score: 0
Accepted
time: 71ms
memory: 4244kb

input:

1
2000 5
100

0.00
0.70

0.00
2.10

0.00
1.20

0.0

1.5 1

output:

5
Ok! 1629 queries used.

result:

points 1.0

Test #12:

score: 0
Accepted
time: 57ms
memory: 4240kb

input:

1
2000 6
100

0.01
0.70

0.00
2.70

0.00
1.90

3.5

1.1 1

output:

6
Ok! 1436 queries used.

result:

points 1.0

Test #13:

score: 0
Accepted
time: 64ms
memory: 4228kb

input:

1
2000 5
100

0.01
1.00

0.10
1.70

0.01
2.30

5.0

1.20 1

output:

5
Ok! 1499 queries used.

result:

points 1.0

Subtask #5:

score: 29
Accepted

Test #14:

score: 29
Accepted
time: 74ms
memory: 4164kb

input:

1
1775 4
100

0.00
0.00

0.00
2.70

0.10
7.55

0.0

1.15 1

output:

4
Ok! 1663 queries used.

result:

points 1.0

Test #15:

score: 0
Accepted
time: 77ms
memory: 4228kb

input:

1
1775 5
100

0.00
1.50

0.00
1.10

0.00
1.75

0.0

1.5 1

output:

5
Ok! 1742 queries used.

result:

points 1.0

Test #16:

score: 0
Accepted
time: 67ms
memory: 4256kb

input:

1
1775 5
100

0.01
1.50

0.00
1.10

0.01
1.75

0.0

1.3 1

output:

5
Ok! 1624 queries used.

result:

points 1.0

Test #17:

score: 0
Accepted
time: 70ms
memory: 4220kb

input:

1
1775 5
100

0.00
0.30

0.00
2.10

0.00
1.75

0.0

1.5 1

output:

5
Ok! 1638 queries used.

result:

points 1.0

Test #18:

score: 0
Accepted
time: 67ms
memory: 4244kb

input:

1
1775 5
100

0.01
0.70

0.00
2.70

0.00
1.90

3.5

1.5 1

output:

5
Ok! 1639 queries used.

result:

points 1.0

Test #19:

score: 0
Accepted
time: 61ms
memory: 4180kb

input:

1
1775 5
100

0.01
1.50

0.00
1.10

0.01
1.75

1.0

1.10 1

output:

5
Ok! 1498 queries used.

result:

points 1.0

Subtask #6:

score: 0
Acceptable Answer

Test #20:

score: 0
Acceptable Answer
time: 78ms
memory: 4240kb

input:

1
1625 5
100

0.00
0.00

0.00
3.00

0.00
1.00

0.0

3 1

output:

0
Too many queries! 1757 out of 1625

result:

points inf0