QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#396875#6749. TargetVictorYuan#AC ✓11ms9304kbC++141.1kb2024-04-23 11:52:282024-04-23 11:52:29

Judging History

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

  • [2024-04-23 11:52:29]
  • 评测
  • 测评结果:AC
  • 用时:11ms
  • 内存:9304kb
  • [2024-04-23 11:52:28]
  • 提交

answer

#include <bits/stdc++.h> 

int main() {
  const int base = 1000000;
  double A, B;
  std::cin >> A >> B;
  int x = A * base, y = B * base;
  std::vector<int> pre(base + 1, -1);
  pre[x] = 0;
  std::queue<int> Q;
  for (Q.push(x); !Q.empty(); Q.pop()) {
    int u = Q.front();
//    std::cerr << u << '\n';
    int v = u >> 1;
    if (pre[v] == -1) {
      pre[v] = u;
      Q.push(v);
    }
    v = (u - base) / 2 + base;
    if (pre[v] == -1) {
      pre[v] = u;
      Q.push(v);
    }
  }
  for (int i = y - 90; i <= y + 90; ++i) if (i >= 0 && i < pre.size() && pre[i] != -1) {
    std::vector<int> ans;
    for (int u = i; u != x; u = pre[u]) {
      if ((pre[u] >> 1) == u) ans.push_back(1);
      else ans.push_back(2);
      if (ans.size() > 50) break;
    }
    if (ans.size() < 50) {
      std::reverse(ans.begin(), ans.end());
      for (auto i : ans) {
        std::cout << i;
        if (i == 1) A = A / 2;
        else A = (A - 1) / 2 + 1;
        std::cerr << std::fixed << A << ' ' << B << '\n';
      }
//      std::cerr << i << '\n';
      return 0;
    }
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 9252kb

input:

0.5 0.25

output:

111212222222222211

result:

ok ok

Test #2:

score: 0
Accepted
time: 7ms
memory: 9168kb

input:

1 0.75

output:

11111212222222222212

result:

ok ok

Test #3:

score: 0
Accepted
time: 9ms
memory: 9304kb

input:

1 0

output:

11111111111111111111

result:

ok ok

Test #4:

score: 0
Accepted
time: 10ms
memory: 8672kb

input:

0.361954 0.578805

output:

21221121111212112

result:

ok ok

Test #5:

score: 0
Accepted
time: 7ms
memory: 8612kb

input:

0.144888 0.140086

output:

221221212222111211

result:

ok ok

Test #6:

score: 0
Accepted
time: 7ms
memory: 9204kb

input:

0.514397 0.969399

output:

121121121111122222

result:

ok ok

Test #7:

score: 0
Accepted
time: 6ms
memory: 8668kb

input:

0.887873 0.402213

output:

11122111222212211221

result:

ok ok

Test #8:

score: 0
Accepted
time: 10ms
memory: 8612kb

input:

0.152004 0.176414

output:

22211121121221211

result:

ok ok

Test #9:

score: 0
Accepted
time: 10ms
memory: 8492kb

input:

0.401831 0.860762

output:

22221121212111222122

result:

ok ok

Test #10:

score: 0
Accepted
time: 10ms
memory: 8584kb

input:

0.580629 0.869474

output:

222222111212222122

result:

ok ok

Test #11:

score: 0
Accepted
time: 10ms
memory: 8588kb

input:

0.138673 0.508844

output:

2122122221112111112

result:

ok ok

Test #12:

score: 0
Accepted
time: 7ms
memory: 8912kb

input:

0.027182 0.263243

output:

1222212122111121

result:

ok ok

Test #13:

score: 0
Accepted
time: 7ms
memory: 8688kb

input:

0.081714 0.212216

output:

2222122112112212211

result:

ok ok

Test #14:

score: 0
Accepted
time: 7ms
memory: 8756kb

input:

0.562775 0.388603

output:

2121222122111221

result:

ok ok

Test #15:

score: 0
Accepted
time: 10ms
memory: 8616kb

input:

0.112949 0.147503

output:

2221122221221211211

result:

ok ok

Test #16:

score: 0
Accepted
time: 3ms
memory: 8652kb

input:

0.800247 0.150903

output:

122212211212211211

result:

ok ok

Test #17:

score: 0
Accepted
time: 10ms
memory: 8300kb

input:

0.300103 0.584619

output:

2122211121221212112

result:

ok ok

Test #18:

score: 0
Accepted
time: 11ms
memory: 8668kb

input:

0.844720 0.070148

output:

22122221112111

result:

ok ok

Test #19:

score: 0
Accepted
time: 10ms
memory: 8824kb

input:

0.573320 0.123035

output:

1212112222122222111

result:

ok ok

Test #20:

score: 0
Accepted
time: 5ms
memory: 8816kb

input:

0.467281 0.231366

output:

121221122122211

result:

ok ok

Test #21:

score: 0
Accepted
time: 10ms
memory: 8512kb

input:

0.264769 0.373434

output:

22212211211222222121

result:

ok ok

Test #22:

score: 0
Accepted
time: 7ms
memory: 8656kb

input:

0.689729 0.570712

output:

11211121211112112112

result:

ok ok

Test #23:

score: 0
Accepted
time: 10ms
memory: 8720kb

input:

0.747218 0.312573

output:

21222222222221121

result:

ok ok

Test #24:

score: 0
Accepted
time: 11ms
memory: 8584kb

input:

0.215052 0.203677

output:

211222211111212211

result:

ok ok

Test #25:

score: 0
Accepted
time: 7ms
memory: 8564kb

input:

0.607834 0.733102

output:

121221121222122212

result:

ok ok

Test #26:

score: 0
Accepted
time: 10ms
memory: 9176kb

input:

0.516860 0.252876

output:

121221221211111121

result:

ok ok

Test #27:

score: 0
Accepted
time: 7ms
memory: 8948kb

input:

0.955285 0.457773

output:

121212121121212221

result:

ok ok

Test #28:

score: 0
Accepted
time: 10ms
memory: 8616kb

input:

0.156178 0.353262

output:

1122112122112122121

result:

ok ok

Test #29:

score: 0
Accepted
time: 10ms
memory: 8644kb

input:

0.398701 0.040258

output:

22211112112112121111

result:

ok ok

Test #30:

score: 0
Accepted
time: 7ms
memory: 9052kb

input:

0.973859 0.000184

output:

12111221111111111111

result:

ok ok

Test #31:

score: 0
Accepted
time: 7ms
memory: 8620kb

input:

0.882213 0.556709

output:

1121222222112221112

result:

ok ok

Test #32:

score: 0
Accepted
time: 6ms
memory: 8492kb

input:

0.263822 0.460984

output:

12122222221212221

result:

ok ok

Test #33:

score: 0
Accepted
time: 7ms
memory: 8848kb

input:

0.443432 0.034841

output:

2121122211121111

result:

ok ok