QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#322648#8215. Isomorphic Delighttriple__a#WA 1ms3996kbC++2010.3kb2024-02-07 13:53:552024-02-07 13:53:56

Judging History

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

  • [2024-02-07 13:53:56]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3996kb
  • [2024-02-07 13:53:55]
  • 提交

answer

// #pragma GCC optimize("trapv")
#include<bits/stdc++.h>
#define int long long
#define i128 __int128_t
using namespace std;

constexpr int P = 998244353;
// constexpr int P = 1e9+7;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x%P)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};
std::vector<int> rev;
std::vector<Z> roots{0, 1};
void dft(std::vector<Z> &a) {
    int n = a.size();
    if ((int)(rev.size()) != n) {
        int k = __builtin_ctz(n) - 1;
        rev.resize(n);
        for (int i = 0; i < n; i++) {
            rev[i] = rev[i >> 1] >> 1 | (i & 1) << k;
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (rev[i] < i) {
            std::swap(a[i], a[rev[i]]);
        }
    }
    if ((int)(roots.size()) < n) {
        int k = __builtin_ctz(roots.size());
        roots.resize(n);
        while ((1 << k) < n) {
            Z e = power(Z(3), (P - 1) >> (k + 1));
            for (int i = 1 << (k - 1); i < (1 << k); i++) {
                roots[2 * i] = roots[i];
                roots[2 * i + 1] = roots[i] * e;
            }
            k++;
        }
    }
    for (int k = 1; k < n; k *= 2) {
        for (int i = 0; i < n; i += 2 * k) {
            for (int j = 0; j < k; j++) {
                Z u = a[i + j];
                Z v = a[i + j + k] * roots[k + j];
                a[i + j] = u + v;
                a[i + j + k] = u - v;
            }
        }
    }
}
void idft(std::vector<Z> &a) {
    int n = a.size();
    std::reverse(a.begin() + 1, a.end());
    dft(a);
    Z inv = (1 - P) / n;
    for (int i = 0; i < n; i++) {
        a[i] *= inv;
    }
}
struct Poly {
    std::vector<Z> a;
    Poly() {}
    explicit Poly(int size, std::function<Z(int)> f = [](int) { return 0; }) : a(size) {
        for (int i = 0; i < size; i++) {
            a[i] = f(i);
        }
    }
    Poly(const std::vector<Z> &a) : a(a) {}
    Poly(const std::initializer_list<Z> &a) : a(a) {}
    int size() const {
        return a.size();
    }
    void resize(int n) {
        a.resize(n);
    }
    Z operator[](int idx) const {
        if (idx < size()) {
            return a[idx];
        } else {
            return 0;
        }
    }
    Z &operator[](int idx) {
        return a[idx];
    }
    Poly mulxk(int k) const {
        auto b = a;
        b.insert(b.begin(), k, 0);
        return Poly(b);
    }
    Poly modxk(int k) const {
        k = std::min(k, size());
        return Poly(std::vector<Z>(a.begin(), a.begin() + k));
    }
    Poly divxk(int k) const {
        if (size() <= k) {
            return Poly();
        }
        return Poly(std::vector<Z>(a.begin() + k, a.end()));
    }
    friend Poly operator+(const Poly &a, const Poly &b) {
        std::vector<Z> res(std::max(a.size(), b.size()));
        for (int i = 0; i < (int)(res.size()); i++) {
            res[i] = a[i] + b[i];
        }
        return Poly(res);
    }
    friend Poly operator-(const Poly &a, const Poly &b) {
        std::vector<Z> res(std::max(a.size(), b.size()));
        for (int i = 0; i < (int)(res.size()); i++) {
            res[i] = a[i] - b[i];
        }
        return Poly(res);
    }
    friend Poly operator-(const Poly &a) {
        std::vector<Z> res(a.size());
        for (int i = 0; i < (int)(res.size()); i++) {
            res[i] = -a[i];
        }
        return Poly(res);
    }
    friend Poly operator*(Poly a, Poly b) {
        if (a.size() == 0 || b.size() == 0) {
            return Poly();
        }
        if (a.size() < b.size()) {
            std::swap(a, b);
        }
        if (b.size() < 128) {
            Poly c(a.size() + b.size() - 1);
            for (int i = 0; i < a.size(); i++) {
                for (int j = 0; j < b.size(); j++) {
                    c[i + j] += a[i] * b[j];
                }
            }
            return c;
        }
        int sz = 1, tot = a.size() + b.size() - 1;
        while (sz < tot) {
            sz *= 2;
        }
        a.a.resize(sz);
        b.a.resize(sz);
        dft(a.a);
        dft(b.a);
        for (int i = 0; i < sz; ++i) {
            a.a[i] = a[i] * b[i];
        }
        idft(a.a);
        a.resize(tot);
        return a;
    }
    friend Poly operator*(Z a, Poly b) {
        for (int i = 0; i < (int)(b.size()); i++) {
            b[i] *= a;
        }
        return b;
    }
    friend Poly operator*(Poly a, Z b) {
        for (int i = 0; i < (int)(a.size()); i++) {
            a[i] *= b;
        }
        return a;
    }
    Poly &operator+=(Poly b) {
        return (*this) = (*this) + b;
    }
    Poly &operator-=(Poly b) {
        return (*this) = (*this) - b;
    }
    Poly &operator*=(Poly b) {
        return (*this) = (*this) * b;
    }
    Poly deriv() const {
        if (a.empty()) {
            return Poly();
        }
        std::vector<Z> res(size() - 1);
        for (int i = 0; i < size() - 1; ++i) {
            res[i] = (i + 1) * a[i + 1];
        }
        return Poly(res);
    }
    Poly integr() const {
        std::vector<Z> res(size() + 1);
        for (int i = 0; i < size(); ++i) {
            res[i + 1] = a[i] / (i + 1);
        }
        return Poly(res);
    }
    Poly inv(int m) const {
        Poly x{a[0].inv()};
        int k = 1;
        while (k < m) {
            k *= 2;
            x = (x * (Poly{2} - modxk(k) * x)).modxk(k);
        }
        return x.modxk(m);
    }
    Poly log(int m) const {
        return (deriv() * inv(m)).integr().modxk(m);
    }
    Poly exp(int m) const {
        Poly x{1};
        int k = 1;
        while (k < m) {
            k *= 2;
            x = (x * (Poly{1} - x.log(k) + modxk(k))).modxk(k);
        }
        return x.modxk(m);
    }
    Poly pow(int k, int m) const {
        int i = 0;
        while (i < size() && a[i].val() == 0) {
            i++;
        }
        if (i == size() || 1LL * i * k >= m) {
            return Poly(std::vector<Z>(m));
        }
        Z v = a[i];
        auto f = divxk(i) * v.inv();
        return (f.log(m - i * k) * k).exp(m - i * k).mulxk(i * k) * power(v, k);
    }
    Poly sqrt(int m) const {
        Poly x{1};
        int k = 1;
        while (k < m) {
            k *= 2;
            x = (x + (modxk(k) * x.inv(k)).modxk(k)) * ((P + 1) / 2);
        }
        return x.modxk(m);
    }
    Poly mulT(Poly b) const {
        if (b.size() == 0) {
            return Poly();
        }
        int n = b.size();
        std::reverse(b.a.begin(), b.a.end());
        return ((*this) * b).divxk(n - 1);
    }
    std::vector<Z> eval(std::vector<Z> x) const {
        if (size() == 0) {
            return std::vector<Z>(x.size(), 0);
        }
        const int n = std::max((int)(x.size()), size());
        std::vector<Poly> q(4 * n);
        std::vector<Z> ans(x.size());
        x.resize(n);
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                q[p] = Poly{1, -x[l]};
            } else {
                int m = (l + r) / 2;
                build(2 * p, l, m);
                build(2 * p + 1, m, r);
                q[p] = q[2 * p] * q[2 * p + 1];
            }
        };
        build(1, 0, n);
        std::function<void(int, int, int, const Poly &)> work = [&](int p, int l, int r, const Poly &num) {
            if (r - l == 1) {
                if (l < (int)(ans.size())) {
                    ans[l] = num[0];
                }
            } else {
                int m = (l + r) / 2;
                work(2 * p, l, m, num.mulT(q[2 * p + 1]).modxk(m - l));
                work(2 * p + 1, m, r, num.mulT(q[2 * p]).modxk(r - m));
            }
        };
        work(1, 0, n, mulT(q[1].inv(n)));
        return ans;
    }
};


const int N=500007;
const int INF=LLONG_MAX/4;
mt19937 rng(1234);

int n;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n;
    if (n==1){cout<<"YES\n0\n"; return 0;}
    if (n<=5){cout<<"NO\n"; return 0;}
    if (n<=6){cout<<"YES\n6\n1 2\n2 3\n1 3\n3 4\n2 5\n5 6\n"; return 0;}
    cout<<"YES\n";
    vector<int> lst;
    lst.push_back(1);
    for (int i=7;i<=5000;++i) lst.push_back(i);
    int sum=0, cur=0;
    while (1){
        if (sum>n) break;
        sum+=lst[cur], cur++; 
    }
    vector<pair<int,int>> ans;
    auto ou=[&](int mx,int n){
        // cerr<<"cerr: "<<mx<<" "<<n<<endl;
        if (n==1) return;
        for (int i=1;i+1<n;++i) ans.push_back({mx-i+1,mx-i});
        ans.push_back({mx-2,mx-n+1});
    };
    // cerr<<cur<<endl;
    for (int i=0;i+2<cur;++i){
        ou(n,lst[i]), n-=lst[i];
    }
    ou(n,n);
    cout<<ans.size()<<"\n";
    for (auto [u,v]:ans) cout<<u<<" "<<v<<"\n";
}



详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

6

output:

YES
6
1 2
2 3
1 3
3 4
2 5
5 6

result:

ok Everything ok

Test #3:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

4

output:

NO

result:

ok Everything ok

Test #4:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

2

output:

NO

result:

ok Everything ok

Test #5:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

3

output:

NO

result:

ok Everything ok

Test #6:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

5

output:

NO

result:

ok Everything ok

Test #7:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

7

output:

YES
6
7 6
6 5
5 4
4 3
3 2
5 1

result:

ok Everything ok

Test #8:

score: 0
Accepted
time: 0ms
memory: 3960kb

input:

8

output:

YES
6
7 6
6 5
5 4
4 3
3 2
5 1

result:

ok Everything ok

Test #9:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

9

output:

YES
7
8 7
7 6
6 5
5 4
4 3
3 2
6 1

result:

ok Everything ok

Test #10:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

10

output:

YES
8
9 8
8 7
7 6
6 5
5 4
4 3
3 2
7 1

result:

ok Everything ok

Test #11:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

11

output:

YES
9
10 9
9 8
8 7
7 6
6 5
5 4
4 3
3 2
8 1

result:

ok Everything ok

Test #12:

score: 0
Accepted
time: 0ms
memory: 3960kb

input:

12

output:

YES
10
11 10
10 9
9 8
8 7
7 6
6 5
5 4
4 3
3 2
9 1

result:

ok Everything ok

Test #13:

score: 0
Accepted
time: 0ms
memory: 3956kb

input:

13

output:

YES
11
12 11
11 10
10 9
9 8
8 7
7 6
6 5
5 4
4 3
3 2
10 1

result:

ok Everything ok

Test #14:

score: 0
Accepted
time: 0ms
memory: 3996kb

input:

14

output:

YES
12
13 12
12 11
11 10
10 9
9 8
8 7
7 6
6 5
5 4
4 3
3 2
11 1

result:

ok Everything ok

Test #15:

score: 0
Accepted
time: 0ms
memory: 3996kb

input:

15

output:

YES
13
14 13
13 12
12 11
11 10
10 9
9 8
8 7
7 6
6 5
5 4
4 3
3 2
12 1

result:

ok Everything ok

Test #16:

score: 0
Accepted
time: 0ms
memory: 3700kb

input:

16

output:

YES
13
15 14
14 13
13 12
12 11
11 10
13 9
8 7
7 6
6 5
5 4
4 3
3 2
6 1

result:

ok Everything ok

Test #17:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

17

output:

YES
14
16 15
15 14
14 13
13 12
12 11
14 10
9 8
8 7
7 6
6 5
5 4
4 3
3 2
7 1

result:

ok Everything ok

Test #18:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

18

output:

YES
15
17 16
16 15
15 14
14 13
13 12
15 11
10 9
9 8
8 7
7 6
6 5
5 4
4 3
3 2
8 1

result:

ok Everything ok

Test #19:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

19

output:

YES
16
18 17
17 16
16 15
15 14
14 13
16 12
11 10
10 9
9 8
8 7
7 6
6 5
5 4
4 3
3 2
9 1

result:

ok Everything ok

Test #20:

score: -100
Wrong Answer
time: 1ms
memory: 3996kb

input:

598

output:

YES
569
597 596
596 595
595 594
594 593
593 592
595 591
590 589
589 588
588 587
587 586
586 585
585 584
588 583
582 581
581 580
580 579
579 578
578 577
577 576
576 575
580 574
573 572
572 571
571 570
570 569
569 568
568 567
567 566
566 565
571 564
563 562
562 561
561 560
560 559
559 558
558 557
557 ...

result:

wrong answer contestant's solution is worse (more edges) than jury's