(cache)Submission #66340777 - AtCoder Beginner Contest 408

Contest Duration: 2025-05-31(Sat) 21:00 - 2025-05-31(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #66340777

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using i128 = __int128_t;
using ull = unsigned long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        ull A, B, C, D;
        cin >> A >> B >> C >> D;
        ull ln = 0, ld = 1;
        ull hn = 1, hd = 0;
        ull answer_q = 0;
        while (true) {
            ull mn = ln + hn;
            ull md = ld + hd;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
using i128 = __int128_t;
using ull = unsigned long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        ull A, B, C, D;
        cin >> A >> B >> C >> D;

        ull ln = 0, ld = 1;
        ull hn = 1, hd = 0;
        ull answer_q = 0;

        while (true) {
            ull mn = ln + hn;
            ull md = ld + hd;

            bool mediant_le_L = ((i128)mn * B <= (i128)md * A);
            if (mediant_le_L) {
                i128 numL = (i128)ld * A - (i128)ln * B;
                i128 denL = (i128)hn * B - (i128)hd * A;
                ull t = (ull)(numL / denL);
                if (t == 0) t = 1;
                ln += t * hn;
                ld += t * hd;
            } else {
                bool mediant_ge_R = ((i128)mn * D >= (i128)md * C);
                if (mediant_ge_R) {
                    i128 numR = (i128)hn * D - (i128)hd * C;
                    i128 denR = (i128)ld * C - (i128)ln * D;
                    ull t = (ull)(numR / denR);
                    if (t == 0) t = 1;
                    hn += t * ln;
                    hd += t * ld;
                } else {
                    answer_q = md;
                    break;
                }
            }
        }
        cout << answer_q;
        if (T) cout << "\n";
    }
    return 0;
}

Submission Info

Submission Time	2025-05-31 21:46:10
Task	G - A/B < p/q < C/D
User	OYU__0YU
Language	C++ 20 (gcc 12.2)
Score	625
Code Size	1447 Byte
Status	AC
Exec Time	221 ms
Memory	4476 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

625 / 625

Status

× 1

× 35

Set Name	Test Cases
Sample	00_sample_00.txt
All	00_sample_00.txt, 01_handmade_00.txt, 01_handmade_01.txt, 01_handmade_02.txt, 01_handmade_03.txt, 01_handmade_04.txt, 01_handmade_05.txt, 01_handmade_06.txt, 01_handmade_07.txt, 01_handmade_08.txt, 01_handmade_09.txt, 01_handmade_10.txt, 01_handmade_11.txt, 01_handmade_12.txt, 01_handmade_13.txt, 01_handmade_14.txt, 01_handmade_15.txt, 02_random_00.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 02_random_05.txt, 02_random_06.txt, 02_random_07.txt, 02_random_08.txt, 02_random_09.txt, 02_random_10.txt, 02_random_11.txt, 02_random_12.txt, 02_random_13.txt, 02_random_14.txt, 02_random_15.txt, 02_random_16.txt, 02_random_17.txt

Case Name	Status	Exec Time	Memory
00_sample_00.txt	AC	1 ms	3476 KiB
01_handmade_00.txt	AC	10 ms	3324 KiB
01_handmade_01.txt	AC	1 ms	3504 KiB
01_handmade_02.txt	AC	221 ms	4252 KiB
01_handmade_03.txt	AC	203 ms	4232 KiB
01_handmade_04.txt	AC	201 ms	4232 KiB
01_handmade_05.txt	AC	110 ms	3516 KiB
01_handmade_06.txt	AC	59 ms	4476 KiB
01_handmade_07.txt	AC	107 ms	3508 KiB
01_handmade_08.txt	AC	114 ms	3508 KiB
01_handmade_09.txt	AC	60 ms	4204 KiB
01_handmade_10.txt	AC	58 ms	4248 KiB
01_handmade_11.txt	AC	59 ms	4244 KiB
01_handmade_12.txt	AC	58 ms	4172 KiB
01_handmade_13.txt	AC	60 ms	4164 KiB
01_handmade_14.txt	AC	57 ms	4212 KiB
01_handmade_15.txt	AC	56 ms	4064 KiB
02_random_00.txt	AC	114 ms	3500 KiB
02_random_01.txt	AC	115 ms	3432 KiB
02_random_02.txt	AC	114 ms	3508 KiB
02_random_03.txt	AC	114 ms	3428 KiB
02_random_04.txt	AC	115 ms	3484 KiB
02_random_05.txt	AC	115 ms	3516 KiB
02_random_06.txt	AC	108 ms	3516 KiB
02_random_07.txt	AC	108 ms	3436 KiB
02_random_08.txt	AC	103 ms	3484 KiB
02_random_09.txt	AC	103 ms	3428 KiB
02_random_10.txt	AC	111 ms	3628 KiB
02_random_11.txt	AC	111 ms	3372 KiB
02_random_12.txt	AC	112 ms	3564 KiB
02_random_13.txt	AC	111 ms	3496 KiB
02_random_14.txt	AC	110 ms	3576 KiB
02_random_15.txt	AC	110 ms	3488 KiB
02_random_16.txt	AC	71 ms	3444 KiB
02_random_17.txt	AC	72 ms	3432 KiB