QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203246#6744. Squareeuphria#AC ✓19ms3492kbC++201.2kb2023-10-06 16:22:572023-10-06 16:22:57

Judging History

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

  • [2023-10-06 16:22:57]
  • 评测
  • 测评结果:AC
  • 用时:19ms
  • 内存:3492kb
  • [2023-10-06 16:22:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
const int N = 1e6 + 10;
const int M = 131;
const int INF = 0x3f3f3f3f;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
const long long mod = 1e9 + 7;

ll cal(ll x){
    ll res = sqrt(2ll * x);
    while(res * (res + 1) < 2ll * x) res++;
    while(res * (res - 1) > 2ll * x) res--;
    return res;
}

void solve(){
    ll x, y; cin >> x >> y;
    if(x >= y){
        cout << x - y << '\n'; return ;
    }
    ll a = cal(x), b = x - a * (a - 1) / 2 - 1;
    ll c = cal(y), d = y - c * (c - 1) / 2 - 1;
    //cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
    ll num1 = a - b, num2 = c - d;
    //cout << num1 << ' ' << num2 << '\n';
    if(num1 <= num2){
        cout << c - a + num2 - num1 << '\n';
    }
    else{
        cout << c - a + 1 + b + c - d << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(12);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0 - 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3444kb

input:

2
5 1
1 5

output:

4
3

result:

ok 2 number(s): "4 3"

Test #2:

score: 0
Accepted
time: 19ms
memory: 3492kb

input:

100000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 ...

output:

0
2
1
4
3
2
6
5
4
3
8
7
6
5
4
10
9
8
7
6
5
12
11
10
9
8
7
6
14
13
12
11
10
9
8
7
16
15
14
13
12
11
10
9
8
18
17
16
15
14
13
12
11
10
9
20
19
18
17
16
15
14
13
12
11
10
22
21
20
19
18
17
16
15
14
13
12
11
24
23
22
21
20
19
18
17
16
15
14
13
12
26
25
24
23
22
21
20
19
18
1
0
2
2
1
3
4
3
2
4
6
5
4
3
5
...

result:

ok 100000 numbers