QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#96502 | #5154. ETA | IsaacMoris# | WA | 8ms | 3460kb | C++14 | 1.5kb | 2023-04-13 23:20:24 | 2023-04-13 23:20:26 |
Judging History
answer
#include<iostream>
#include <bits/stdc++.h>
# define ld long double
#define ll long long
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e6 + 5, mod = 998244353, M = 17;
int a, b;
bool good(ll sum, ll base) {
// sum / base >= a/b
return sum * b >= a * base;
}
void getInput() {
string s;
cin >> s;
bool f = false;
for (auto i: s) {
if (i == '/')f = true;
else {
if (!f) a = a * 10 + i - '0';
else b = b * 10 + i - '0';
}
}
}
void doWork() {
getInput();
int g = __gcd(a, b);
a /= g;
b /= g;
int lvl = 2000;
vector<int> cnt(lvl + 1, 1);
cnt.back() = 3000 / b * b - lvl;
ll sum = (lvl - 1) * (lvl - 2) / 2 + lvl * cnt.back();
ll base = 3000 / b * b;
for (int i = cnt.size() - 1; i >= 2; i--) {
while (cnt[i] && good(sum - 1, base)) {
cnt[i]--;
cnt[i - 1]++;
sum--;
}
}
if (sum * b != a * base) {
cout << "impossible";
return;
}
cout << base << " " << base - 1 << "\n";
int last = 1;
for (int i = 1; i < cnt.size(); i++) {
for (int j = 1; j <= cnt[i]; j++) {
cout << last << " " << last + j << "\n";
}
last += cnt[i];
}
}
int main() {
IO
int t = 1;
// cin >> t;
for (int i = 1; i <= t; i++) {
doWork();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 8ms
memory: 3460kb
input:
1/2
output:
3000 2999 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 6...
result:
FAIL Wrong average distance, got 3499/3000, wanted 1/2