QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#492264	#9156. 百万富翁	zfs732^#	51.99999	1970ms	84256kb	C++23	1.2kb	2024-07-26 10:56:34	2024-07-26 10:56:34

Judging History

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

[2024-07-26 10:56:34]
评测

测评结果：51.99999
用时：1970ms
内存：84256kb

查看

[2024-07-26 10:56:34]
提交

answer

#include "richest.h"
#include <bits/stdc++.h>

int Force(std::vector<int> id) {
  int N = (int) id.size();
  std::vector g(N, std::vector<bool>(N));
  std::vector<int> A, B;
  for (int i = 0; i < N; i++)
    for (int j = i + 1; j < N; j++) {
      A.emplace_back(id[i]);
      B.emplace_back(id[j]);
    }
  auto res = ask(A, B);
  for (int i = 0, tot = 0; i < N; i++)
    for (int j = i + 1; j < N; j++) {
      int c = res[tot++] == id[i];
      g[i][j] = c, g[j][i] = !c;
    }
  for (int i = 0; i < N; i++) {
    int cnt = 0;
    for (int j = 0; j < N; j++)
      cnt += g[i][j];
    if (cnt == N - 1)
      return id[i];
  }
  return -1;
}

int richest(int N, int T, int S) {
  std::vector<int> cur;
  for (int i = 0; i < N; i++)
    cur.emplace_back(i);

  if (T == 1) return Force(cur);

  while (cur.size() > 400) {
    int m = (int) cur.size(), ext = -1;
    std::vector<int> A, B;

    for (int i = 0; i + 1 < m; i += 2) {
      A.emplace_back(cur[i]);
      B.emplace_back(cur[i ^ 1]);
    }

    if (m & 1) ext = cur.back();
    cur = ask(A, B);
    if (~ext) cur.emplace_back(ext);
  }

  return Force(cur);
}

/*
 * 1000000 20 2000000 1
 * 10000 20 2000000 1
 */

源文件, 语言: C++23

详细

Pretests

Pretest #1:

score: 15

Accepted

time: 619ms

memory: 25188kb

input:

1000 1 499500 957319859

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Pretest #2:

score: 37

Acceptable Answer

time: 1970ms

memory: 84256kb

input:

1000000 20 2000000 29091473

output:

Partially correct Case 2, 37 / 85, maxt = 13, maxs = 1029645
14233204743512706019
0.435294
13281437197936769557

result:

points 0.435294 Partially correct Case 2, 37 / 85, maxt = 13, maxs = 1029645

Final Tests

Test #1:

score: 15

Accepted

time: 627ms

memory: 23168kb

input:

1000 1 499500 957319857

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Test #2:

score: 37

Acceptable Answer

time: 1961ms

memory: 84208kb

input:

1000000 20 2000000 29091471

output:

Partially correct Case 2, 37 / 85, maxt = 13, maxs = 1029645
14233204743512706019
0.435294
13281437197936769557

result:

points 0.435294 Partially correct Case 2, 37 / 85, maxt = 13, maxs = 1029645