QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#226720 | #5154. ETA | Fyind# | WA | 0ms | 17504kb | C++23 | 1.8kb | 2023-10-26 14:33:46 | 2023-10-26 14:33:46 |
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 = 5e5 + 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;
if (a == b-1) {
n = b;
t = a;
} else {
t = a*1000;
n = b*1000;
}
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: 17244kb
input:
1/2
output:
2 1 1 2
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 17160kb
input:
1/3
output:
impossible
result:
ok
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 17504kb
input:
7/4
output:
4000 3999 3923 3924 3924 3925 3922 3925 3925 3926 3926 3927 3927 3928 3928 3929 3929 3930 3930 3931 3931 3932 3932 3933 3933 3934 3934 3935 3935 3936 3936 3937 3937 3938 3938 3939 3939 3940 3940 3941 3941 3942 3942 3943 3943 3944 3944 3945 3945 3946 3946 3947 3947 3948 3948 3949 3949 3950 3950 3951 ...
result:
FAIL Wrong average distance, got 10998/4000, wanted 7/4