QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#207092#5154. ETAMinhhoWA 0ms3812kbC++201.3kb2023-10-08 09:17:442023-10-08 09:17:45

Judging History

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

  • [2023-10-08 09:17:45]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3812kb
  • [2023-10-08 09:17:44]
  • 提交

answer

#define taskname "E"
#include <bits/stdc++.h>
#define ii pair<int,int>
#define ff first
#define ss second

using namespace std;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int x = 0, y = 0;
    string s;
    cin>>s;
    for (char c: s)
    {
        if (c != '/')
        {
            int a = c - '0';
            x = x * 10 + a;
        }
        else swap(x, y);
    }
    swap(x, y);
    if (y - x > 1 || max(x, y) == 1) return cout<<"impossible", 0;
//    cout<<"BEF: "<<x<<" "<<y<<"\n";
    int cx = x, cy = y;
    while (2 * x > y * (y - 1)) y += cy, x += cx;
//    cout<<x<<" "<<y<<"\n";
    /**
    dep * (dep + 1) / 2 <= x
    **/
    int dep = sqrt(2*x);
    if (dep * (dep + 1) > x) dep--;
    vector<ii> e;
    while ((x - dep * (dep + 1) / 2) < (y - dep - 1)) dep--;
    int cnt = dep + 1;
    for (int i=2; i<=cnt; i++) e.emplace_back(i-1, i);
    x -= dep * (dep+1) / 2;
    int rem = y - dep - 1;
    while (x > rem)
    {
        int mdep = min(dep, x + 1 - rem);
        e.emplace_back(++cnt, mdep);
        x -= mdep;
        rem--;
    }
    assert(x == rem);
    for (int i=1; i<=x; i++) e.emplace_back(++cnt, 1);
    cout<<cnt<<" "<<e.size()<<"\n";
    for (auto [u, v]: e) cout<<u<<" "<<v<<"\n";
}

详细

Test #1:

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

input:

1/2

output:

2 1
2 1

result:

ok 

Test #2:

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

input:

1/3

output:

impossible

result:

ok 

Test #3:

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

input:

7/4

output:

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

result:

ok 

Test #4:

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

input:

974/975

output:

975 974
1 2
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 1
...

result:

ok 

Test #5:

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

input:

943/346

output:

346 345
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
37 4
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...

result:

ok 

Test #6:

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

input:

912/7

output:

266 265
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
52 ...

result:

ok 

Test #7:

score: -100
Wrong Answer
time: 0ms
memory: 3812kb

input:

1/1

output:

impossible

result:

wrong output format Expected integer, but "impossible" found