QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#631485#511. Differencechuchu#AC ✓177ms28296kbC++20750b2024-10-12 07:50:282024-10-12 07:50:29

Judging History

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

  • [2024-10-12 07:50:29]
  • 评测
  • 测评结果:AC
  • 用时:177ms
  • 内存:28296kb
  • [2024-10-12 07:50:28]
  • 提交

answer

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

const int MAX = 2e8+500;

void solve() {
    bitset<MAX> s;
    vector<int> pr;
    int d = 1;
    int x, goal; cin >> x >> goal;
    s[x] = 1;
    s[0] = 1;
    pr.push_back(x);
    if (x == goal) {
        cout << 1 << endl;
        return;
    }
    for (int i = 2; ; ++i) {
        while (s[d]) d++; 
        x += d;
        s[x] = 1;
        for (auto y : pr) s[x-y] = 1;
        pr.push_back(x);       
        // cerr << x << endl;
        if (s[goal]) {
            cout << i << endl;
            return;
        }
    }
}

int main() {
    cin.tie(0);
    cin.sync_with_stdio(0);

	int t = 1;
    // cin >> t;
	while (t--) solve();
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 27956kb

input:

1 5

output:

4

result:

ok single line: '4'

Test #2:

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

input:

1 12

output:

4

result:

ok single line: '4'

Test #3:

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

input:

5 1

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 8ms
memory: 28016kb

input:

1 1

output:

1

result:

ok single line: '1'

Test #5:

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

input:

1 100

output:

42

result:

ok single line: '42'

Test #6:

score: 0
Accepted
time: 177ms
memory: 28060kb

input:

1 39129

output:

10000

result:

ok single line: '10000'

Test #7:

score: 0
Accepted
time: 171ms
memory: 28064kb

input:

1 99984544

output:

10000

result:

ok single line: '10000'

Test #8:

score: 0
Accepted
time: 166ms
memory: 28296kb

input:

1 188286782

output:

10000

result:

ok single line: '10000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 27908kb

input:

100 1

output:

2

result:

ok single line: '2'

Test #10:

score: 0
Accepted
time: 0ms
memory: 27996kb

input:

100 100

output:

1

result:

ok single line: '1'

Test #11:

score: 0
Accepted
time: 169ms
memory: 28128kb

input:

100 38961

output:

10000

result:

ok single line: '10000'

Test #12:

score: 0
Accepted
time: 164ms
memory: 28072kb

input:

100 99940474

output:

10000

result:

ok single line: '10000'

Test #13:

score: 0
Accepted
time: 167ms
memory: 28128kb

input:

100 186474736

output:

10000

result:

ok single line: '10000'

Test #14:

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

input:

92 11942

output:

3390

result:

ok single line: '3390'

Test #15:

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

input:

10 12050

output:

170

result:

ok single line: '170'

Test #16:

score: 0
Accepted
time: 8ms
memory: 28040kb

input:

97 177304

output:

668

result:

ok single line: '668'

Test #17:

score: 0
Accepted
time: 13ms
memory: 28212kb

input:

55 2943751

output:

3653

result:

ok single line: '3653'

Test #18:

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

input:

64 4643557

output:

1932

result:

ok single line: '1932'

Test #19:

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

input:

20 13108321

output:

2861

result:

ok single line: '2861'

Test #20:

score: 0
Accepted
time: 14ms
memory: 28016kb

input:

95 4026722

output:

4391

result:

ok single line: '4391'

Test #21:

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

input:

77 3040555

output:

1407

result:

ok single line: '1407'

Test #22:

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

input:

4 3561761

output:

5030

result:

ok single line: '5030'

Test #23:

score: 0
Accepted
time: 104ms
memory: 28000kb

input:

38 122564001

output:

8354

result:

ok single line: '8354'

Test #24:

score: 0
Accepted
time: 95ms
memory: 28124kb

input:

95 89195320

output:

8396

result:

ok single line: '8396'

Test #25:

score: 0
Accepted
time: 146ms
memory: 28164kb

input:

60 149297808

output:

9686

result:

ok single line: '9686'

Test #26:

score: 0
Accepted
time: 156ms
memory: 28292kb

input:

65 19852042

output:

9732

result:

ok single line: '9732'

Test #27:

score: 0
Accepted
time: 159ms
memory: 28292kb

input:

3 152881363

output:

9778

result:

ok single line: '9778'

Test #28:

score: 0
Accepted
time: 155ms
memory: 28076kb

input:

41 182614945

output:

9823

result:

ok single line: '9823'

Test #29:

score: 0
Accepted
time: 156ms
memory: 28072kb

input:

27 110436294

output:

9872

result:

ok single line: '9872'

Test #30:

score: 0
Accepted
time: 167ms
memory: 28072kb

input:

87 174372628

output:

9938

result:

ok single line: '9938'