QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#201514 | #5154. ETA | DreamOn# | WA | 0ms | 3948kb | C++23 | 1.2kb | 2023-10-05 14:53:14 | 2023-10-05 14:53:14 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define Maxn 1000005
using namespace std;
int a, b, n, m, ans[Maxn];
int gcd(int x, int y) {
if(x < y) swap(x, y);
if(!y) return x;
else return gcd(y, x % y);
}
int main() {
scanf("%d/%d", &a, &b);
int gcdab = gcd(a, b); a /= gcdab, b /= gcdab;
if(a < b) {
if(a == b - 1) {
n = b, m = b - 1;
printf("%d %d\n", n, m);
for(int i = 1; i <= m; ++i) printf("%d %d\n", 1, i + 1);
}
else printf("Impossible\n");
return 0;
}
int k = ceil((2 * a + b) * 1.0 / b / b);
n = k * b, m = n - 1;
int restSum = a * k, restVer = n - 1, tot = 0;
while(restVer) {
int cur = 1;
while(cur * (cur + 1) / 2 + (restVer - cur) <= restSum) ++cur;
--cur;
ans[++tot] = cur;
restSum -= cur * (cur + 1) / 2, restVer -= cur;
}
printf("%d %d\n", n, m);
int u = 2;
for(int i = 1; i <= tot; ++i) {
printf("1 %d\n", u); ++u;
for(int j = 2; j <= ans[i]; ++j) {
printf("%d %d\n", u - 1, u); ++u;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3948kb
input:
1/2
output:
2 1 1 2
result:
ok
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3736kb
input:
1/3
output:
Impossible
result:
wrong answer Token "Impossible" doesn't correspond to pattern "impossible"