QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#486421#5154. ETALongvuWA 1ms3868kbC++143.1kb2024-07-21 19:49:322024-07-21 19:49:32

Judging History

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

  • [2024-07-21 19:49:32]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3868kb
  • [2024-07-21 19:49:32]
  • 提交

answer

/**
 *    author:  longvu
 *    created: 07/21/24 16:35:51
**/
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
const int INF = numeric_limits<int>::max();
const int nax = (int)(100001);
const int mod = 1e9 + 7;

template<class X, class Y>
bool maximize(X& x, const Y y) {
    if (y > x) {x = y; return true;}
    return false;
}
template<class X, class Y>
bool minimize(X& x, const Y y) {
    if (y < x) {x = y; return true;}
    return false;
}

int gcd(int a, int b) {
    return (!b ? a : gcd(b, a % b));
}

int d[nax];
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int x = 0, y = 0;
    for (int i = 0; i < sz(s); ++i) {
        if (s[i] == '/') {
            for (int j = 0; j < i; ++j) {
                x = 10 * x + (s[j] - '0');
            }
            for (int j = i + 1; j < sz(s); ++j) {
                y = 10 * y + (s[j] - '0');
            }
        }
    }
    int _gcd = gcd(x, y);
    x /= _gcd;
    y /= _gcd;
    if (x >= 2 && y == 1) {
        cout << 2 * x + 1 << " " << 2 * x << '\n';
        for (int i = 2; i <= 2 * x; ++i) {
            cout << i - 1 << " " << i << '\n';
        }
        exit(0);
    }
    int a = x, b = y;
    while (a <= 1e6 && b <= 1e6) {
        if (a >= b - 1 && (b - 1) * b / 2 >= a) {
            int z = a, t = b;
            b--;
            int g = 0;
            for (int i = b - 1; i >= 1; --i) {
                if (b - 1 - i <= a - i * (i + 1) / 2) {
                    g = i;
                    for (int j = 1; j <= i; ++j) {
                        d[j]++;
                        a -= j;
                    }
                    b -= i;
                    break;
                }
            }
            int need = a - (b - 1);
            d[need]++;
            a -= need;
            b--;
            if (!need) {
                d[g]--;
                d[g - 1]++;
                d[1]++;
                g--;
            }
            for (int i = 1; i <= b; ++i) {
                d[1]++;
            }
            // cout << a << " " << g << '\n';
            int h = 0;
            for (int i = 1; i <= t; ++i) {
                h += d[i];
            }
            // cout << "BU" << '\n';
            // for (int i = 1; i <= t; ++i) {
            //     cout << d[i] << " ";
            // }
            // cout << '\n';
            int sum = 0;
            for (int i = 1; i <= t; ++i) {
                sum += i * d[i];
            }
            assert(sum == z);
            cout << t << " " << h << '\n';
            int num = g + 1;
            for (int i = 1; i <= t; ++i) {
                if (!d[i]) {
                    break;
                }
                cout << i << " " << i + 1 << '\n';
                for (int j = 2; j <= d[i]; ++j) {
                    cout << i << " " << ++num << '\n';
                }
            }
            exit(0);
        }
        a += x;
        b += y;
    }
    cout << "impossible" << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3868kb

input:

1/2

output:

2 1
1 2

result:

ok 

Test #2:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

1/3

output:

impossible

result:

ok 

Test #3:

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

input:

7/4

output:

8 7
1 2
1 6
1 7
2 3
2 8
3 4
4 5

result:

ok 

Test #4:

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

input:

974/975

output:

975 974
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 61
...

result:

ok 

Test #5:

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

input:

943/346

output:

346 345
1 2
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 61
1 62
1 63
1 64
1 65
1 66
1 67
1 68
1 69
1 70
1 71
1 72
1 73
1 74
1 75
1 76
1 77
1 78
1 79
1 80
1 81
1 82
1 83
1 84
1 85
1 86
1 87
1 88
1 89
1 90
1 91
1 92
1 93
1 9...

result:

ok 

Test #6:

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

input:

912/7

output:

266 265
1 2
1 264
1 265
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 ...

result:

ok 

Test #7:

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

input:

1/1

output:

3 2
1 2
2 3

result:

ok 

Test #8:

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

input:

1/1000

output:

impossible

result:

ok 

Test #9:

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

input:

1000/999

output:

999 998
1 2
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 61
1 62...

result:

ok 

Test #10:

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

input:

999/1000

output:

1000 999
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 61...

result:

ok 

Test #11:

score: -100
Wrong Answer
time: 1ms
memory: 3644kb

input:

1000/1

output:

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

result:

wrong output format Unexpected end of file - int32 expected