QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#226703 | #5154. ETA | Fyind# | WA | 4ms | 16388kb | C++23 | 1.3kb | 2023-10-26 14:11:19 | 2023-10-26 14:11:19 |
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 main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int a; cin >> a;
char c; cin >> c;
int b; cin >> b;
int t = a*b;
int n = b*b;
if (a < b-1) {
cout << "impossible\n";
return 0;
}
if (a == b-1) {
n = b;
t = a;
}
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';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 15604kb
input:
1/2
output:
2 1 1 2
result:
ok
Test #2:
score: 0
Accepted
time: 2ms
memory: 15968kb
input:
1/3
output:
impossible
result:
ok
Test #3:
score: -100
Wrong Answer
time: 4ms
memory: 16388kb
input:
7/4
output:
16 15 11 12 12 13 10 13 13 14 14 15 15 16 1 16 2 16 3 16 4 16 5 16 6 16 7 16 8 16 9 16
result:
FAIL Wrong average distance, got 42/16, wanted 7/4