QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#207092 | #5154. ETA | Minhho | WA | 0ms | 3812kb | C++20 | 1.3kb | 2023-10-08 09:17:44 | 2023-10-08 09:17:45 |
Judging History
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