QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#226726 | #5154. ETA | Fyind# | WA | 0ms | 27708kb | C++23 | 1.9kb | 2023-10-26 14:43:21 | 2023-10-26 14:43:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define _ <<" "<<
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 1e6 + 5;
int n, m;
vector<int> G[maxn];
int id[maxn];
void addedge(int a,int b) {
G[a].push_back(b);
G[b].push_back(a);
}
vector<pii> ans;
void dfs(int x,int fa) {
for (auto v : G[x]) if (v != fa) {
dfs(v, x);
ans.push_back({v, x});
}
}
int sum = 0;
void varify(int x,int fa,int dep) {
sum += dep;
for (auto v : G[x]) if (v != fa) {
varify(v, x, dep+1);
}
}
void solve(int a,int b) {
if (a < b-1) {
cout << "impossible\n";
return;
}
int t,n;
for (int p = 1;p <= 1000000; ++p) if (p*b <= 1000000) {
ll cur = (ll)(b*p-1)*b*p/2;
if (a*p >= b*p - 1 && a*p <= cur) {
n = b*p;
t = a*p;
break;
}
}
// for (int i = 1;i <= n; ++i) G[i].clear();
// memset(id,0,sizeof(id));
ans.clear();
int tar = t;
int k = n;
int maxdep = 0;
id[0] = n; k--;
int mx = n;
// cout << "Tar" _ t _ k << endl;
while (k <= t-maxdep) {
addedge(k,mx); mx = k;
id[++maxdep] = k;
k--;
t -= maxdep;
}
// cout << "Tar" _ t _ k << endl;
for (int i = 1;i < k; ++i) {
addedge(n, i);
t--;
}
// cout << "Tar" _ t _ k << endl;
addedge(id[t-1], k);
dfs(n,0);
cout << n _ n-1 << '\n';
for (auto [a,b] : ans) {
cout << a _ b << '\n';
}
// sum = 0;
// varify(n,0,0);
// cout << sum _ tar << endl;
// assert(sum == tar);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int a; cin >> a;
char c; cin >> c;
int b; cin >> b;
solve(a,b);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 27268kb
input:
1/2
output:
2 1 1 2
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 27708kb
input:
1/3
output:
impossible
result:
ok
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 27164kb
input:
7/4
output:
8 7 4 5 5 6 6 7 3 7 7 8 1 8 2 8
result:
FAIL Wrong average distance, got 20/8, wanted 7/4