QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226703#5154. ETAFyind#WA 4ms16388kbC++231.3kb2023-10-26 14:11:192023-10-26 14:11:19

Judging History

你现在查看的是最新测评结果

  • [2023-10-26 14:11:19]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:16388kb
  • [2023-10-26 14:11:19]
  • 提交

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