QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#226720#5154. ETAFyind#WA 0ms17504kbC++231.8kb2023-10-26 14:33:462023-10-26 14:33:46

Judging History

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

  • [2023-10-26 14:33:46]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:17504kb
  • [2023-10-26 14:33:46]
  • 提交

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;
}

详细

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