QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#96276 | #5154. ETA | RoomGamadan# | WA | 2ms | 3528kb | C++20 | 1.4kb | 2023-04-13 18:32:31 | 2023-04-13 18:32:33 |
Judging History
answer
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define el '\n'
#define F first
#define S second
typedef long long ll;
typedef long double ld;
bool multipleTestCases = 0, sublime = 0;
const int N = 2e3 + 5, INF = 1e9 + 5, mod = 1e9 + 7, LOG = 22, SQ = 500;
int sum, id, rem;
vector<pair<int, int>> edges;
void dfs(int u, int d) {
while (sum >= d + 1 && sum - d - 1 >= rem - 1)
sum -= d + 1, rem--, edges.emplace_back(u, id++), dfs(id - 1, d + 1);
}
void doWork() {
char x, y;
cin >> x >> y >> y;
int a = x - '0', b = y - '0';
if (a < b - 1)
return cout << "impossible", void();
int n;
for (n = b; ; n += b) {
if (n * (n - 1) / 2 >= a * n / b) {
id = 2, sum = a * n / b, rem = n - 1;
dfs(1, 0);
cout << n << ' ' << edges.size() << el;
for (auto &i: edges)
cout << i.first << ' ' << i.second << el;
return;
}
}
}
signed main() {
#ifdef ONLINE_JUDGE
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#endif
#ifndef ONLINE_JUDGE
if (sublime) {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
}
#endif
int tests = 1;
if (multipleTestCases) {
cin >> tests;
}
for (int tc = 1; tc <= tests; tc++) {
doWork();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3380kb
input:
1/2
output:
2 1 1 2
result:
ok
Test #2:
score: 0
Accepted
time: 2ms
memory: 3336kb
input:
1/3
output:
impossible
result:
ok
Test #3:
score: 0
Accepted
time: 2ms
memory: 3376kb
input:
7/4
output:
8 7 1 2 2 3 3 4 4 5 2 6 1 7 1 8
result:
ok
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 3528kb
input:
974/975
output:
8 7 1 2 2 3 3 4 4 5 5 6 2 7 1 8
result:
FAIL Wrong average distance, got 18/8, wanted 974/975