QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#501537#5154. ETAssmyWA 1ms3752kbC++201.7kb2024-08-02 20:24:092024-08-02 20:24:10

Judging History

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

  • [2024-08-02 20:24:10]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3752kb
  • [2024-08-02 20:24:09]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long

void solve()
{
    int a, b;
    char c;
    std:: cin >> a >> c >> b;
    a /= gcd(a, b);
    b /= gcd(a, b);
    if(b - a >= 2)
    {
        std:: cout << "impossible" << endl;
        return ;
    }
    if(b - a == 1)
    {
        std:: cout << b << " " << a << endl;
        for(int i = 2; i <= b; i ++ )
        {
            std:: cout << 1 << " " << i << endl;
        }
        return ;
    }
    int aa = a;
    int bb = b;
    while(((b - 1) * (b) / 2 < a))
    {
        a += aa;
        b += bb;
    }
    if(b > 1000000)
    {
        std:: cout << "impossible" << endl;
        return ;       
    }
    // std:: cout << a << " " << b << endl;
    int n = b;
    vector <int> s;
    b -- ;
    while(1)
    {
        int ans = 1;
        int i;
        for(i = 1; i <= n; i ++ )
        {
            ans = i * (i + 1) / 2;
            if(ans > a)
            {
                break;
            }
        }
        s.push_back(i - 1);
        a -= (i - 1) * i / 2;
        if(a == 0)
        {
            break;
        }
    }
    int sum = 0;

    for(auto p : s)
    {
        sum += p;
    }    

    std:: cout << n << " " << sum << endl;
    int cnt = 2;
    for(auto p : s)
    {
        std:: cout << 1 << " " << cnt << endl;
        for(int i = 2; i <= p; i ++ )
        {
            std:: cout << cnt << " " << cnt + 1 << endl;
            cnt ++ ;
        }
        cnt ++ ;
    }



}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
    // int T;
    // std:: cin >> T;
    // while(T -- )
	solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1/2

output:

2 1
1 2

result:

ok 

Test #2:

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

input:

1/3

output:

impossible

result:

ok 

Test #3:

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

input:

7/4

output:

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

result:

ok 

Test #4:

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

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: -100
Wrong Answer
time: 1ms
memory: 3624kb

input:

943/346

output:

346 53
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
1 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
1 52
52 53
...

result:

FAIL Graph not connected, vertex 55 unreachable