QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#371806#6512. Completely Multiplicative Functionucup-team1191#RE 128ms85848kbC++2011.0kb2024-03-30 16:39:382024-03-30 16:39:39

Judging History

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

  • [2024-03-30 16:39:39]
  • 评测
  • 测评结果：RE
  • 用时：128ms
  • 内存：85848kb
查看
  • [2024-03-30 16:39:38]
  • 提交

answer

/*
    author:  Maksim1744
    created: 30.03.2024 11:18:46
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#define OSTREAM(...)    ;
#define OSTREAM0(...)   ;
#endif

struct Sieve {
    struct PrimeIterator {
        int prime;
        int count;
        int num;
        const Sieve& sieve;

        PrimeIterator(int num, const Sieve& sieve) : num(num), sieve(sieve) {
            step();
        }

        void step() {
            prime = sieve.mn[num];
            count = 0;
            while (num != 1 && sieve.mn[num] == prime) {
                num /= sieve.mn[num];
                ++count;
            }
        }

        bool operator == (const PrimeIterator& other) const {
            return tie(prime, count, num) == tie(other.prime, other.count, other.num);
        }
        bool operator != (const PrimeIterator& other) const {
            return !(*this == other);
        }

        PrimeIterator& operator ++ () {
            step();
            return *this;
        }

        pair<int, int> operator * () const {
            return {prime, count};
        }
    };

    struct PrimeIteratorContainer {
        int num;
        const Sieve& sieve;
        using iterator = PrimeIterator;

        PrimeIteratorContainer(int num, const Sieve& sieve) : num(num), sieve(sieve) {}

        PrimeIterator begin() const {
            return PrimeIterator(num, sieve);
        }

        PrimeIterator end() const {
            return PrimeIterator(1, sieve);
        }

        vector<pair<int, int>> collect() const {
            vector<pair<int, int>> result;
            for (auto p : *this)
                result.push_back(p);
            return result;
        }
    };

    template<typename U, typename V>
    struct DoubleIterator {
        U u;
        V v;
        U::iterator uit;
        V::iterator vit;
        int prime;
        int count;

        DoubleIterator(const U& u, const V& v, U::iterator uit, V::iterator vit) : u(u), v(v), uit(uit), vit(vit) {
            tie(prime, count) = this->operator*();
        }

        DoubleIterator& operator ++ () {
            if (uit == u.end()) {
                ++vit;
            } else if (vit == v.end()) {
                ++uit;
            } else if ((*uit).first < (*vit).first) {
                ++uit;
            } else if ((*uit).first > (*vit).first) {
                ++vit;
            } else {
                ++uit;
                ++vit;
            }
            return *this;
        }

        bool operator == (const DoubleIterator& other) const {
            return tie(uit, vit) == tie(other.uit, other.vit);
        }
        bool operator != (const DoubleIterator& other) const {
            return !(*this == other);
        }

        pair<int, int> operator * () const {
            if (uit == u.end()) return *vit;
            if (vit == v.end()) return *uit;
            if ((*uit).first < (*vit).first) return *uit;
            if ((*uit).first > (*vit).first) return *vit;
            return {(*uit).first, (*uit).second + (*vit).second};
        }
    };

    template<typename U, typename V>
    struct DoubleIteratorContainer {
        using iterator = DoubleIterator<U, V>;
        U u;
        V v;

        DoubleIteratorContainer(const U& u, const V& v) : u(u), v(v) {}

        iterator begin() const {
            return iterator(u, v, u.begin(), v.begin());
        }

        iterator end() const {
            return iterator(u, v, u.end(), v.end());
        }

        vector<pair<int, int>> collect() const {
            vector<pair<int, int>> result;
            for (auto p : *this)
                result.push_back(p);
            return result;
        }
    };

    vector<bool> isp;
    vector<int> primes;
    vector<int> mn;

    Sieve(int n, bool gen_primes = false, bool gen_mn = false) {
        isp.assign(n + 1, true); isp[0] = isp[1] = false;
        for (int i = 2; i * i <= n; ++i)
            if (isp[i])
                for (int j = i * i; j <= n; j += i)
                    isp[j] = false;

        if (gen_primes)
            for (int i = 2; i <= n; ++i)
                if (isp[i])
                    primes.push_back(i);

        if (gen_mn) {
            mn.assign(n + 1, -1);
            for (int i = 2; i <= n; ++i) {
                if (isp[i]) {
                    mn[i] = i;
                    if ((ll)i * i <= n)
                        for (int j = i * i; j <= n; j += i)
                            if (mn[j] == -1)
                                mn[j] = i;
                }
            }
        }
    }

    bool is_prime(int k) const {
        return isp[k];
    }

    bool operator[](int k) const {
        return isp[k];
    }

    // can be used as vector<pair<int, int>>, as in function phi() below
    // except doesn't create a vector to avoid heap allocations
    // can be transformed into vector<pair<int, int>> with .collect()
    auto get_prime_divs(int p) const {
        return PrimeIteratorContainer(p, *this);
    }

    // if you want to get prime divs for n = a * b * c where max(a, b, c) < size(sieve), then call get_prime_divs(a, b, c)
    template<typename... Args>
    auto get_prime_divs(int p, Args... args) const {
        return DoubleIteratorContainer(PrimeIteratorContainer(p, *this), get_prime_divs(args...));
    }

    int phi(int n) const {
        auto v = get_prime_divs(n);
        for (auto [p, c] : v)
            n = n / p * (p - 1);
        return n;
    }
};

const int N = 2e6 + 20;
Sieve sieve(N, true, true);

vector<vector<int>> where(N);


mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 rng(4738268);
ll rnd (ll l, ll r) { return (ll)(rng() % (r - l + 1)) + l; }
ll rnd (ll r)       { return rng() % r; }
ll rnd ()           { return rng(); }
ld rndf()           { return (ld)rng() / (ld)ULLONG_MAX; }
ld rndf(ld l, ld r) { return rndf() * (r - l) + l; }

vector<int> small_primes;
vector<int> large_primes;
void test_case(int test) {
    int n, k;
    cin >> n >> k;
    if (n % 2 != k % 2) {
        cout << -1 << '\n';
        return;
    }
    small_primes.clear();
    large_primes.clear();
    for (int i = 2; i <= n; ++i) {
        if (sieve.is_prime(i)) {
            if (i * 2 <= n) {
                small_primes.pb(i);
            } else {
                large_primes.pb(i);
            }
        }
    }
    int d = large_primes.size();
    vector<int> vals(n + 1, 0);
    int s;
    while (true) {
        vals.assign(vals.size(), 0);
        vals[1] = 1;
        ld prob = (ld)k / n;
        for (int i = 2; i <= n; ++i) {
            if (sieve.is_prime(i)) {
                if (i * 2 <= n) {
                    vals[i] = (rndf() < prob) ? 1 : -1;
                } else {
                    vals[i] = 0;
                }
            } else {
                int p = (*sieve.get_prime_divs(i).begin()).first;
                vals[i] = vals[i / p] * vals[p];
            }
        }
        s = sum(vals);
        assert(s == k || !small_primes.empty());
        show(small_primes, large_primes);
        // cerr << d << endl;
        int its = 0;
        int bad = 0;
        while (abs(s - k) > d && bad < 100) {
            ++its;
            // cerr << abs(s - k) << ' ';
            show(vals);
            show(s, k, d);
            int i = small_primes[rnd(small_primes.size())];
            int was = s;
            for (int j : where[i]) {
                if (j > n) break;
                s -= vals[j] * 2;
                vals[j] = -vals[j];
            }
            if (abs(s - k) >= abs(was - k)) {
                ++bad;
            } else {
                bad = 0;
            }
            if (abs(s - k) > abs(was - k)) {
                for (int j : where[i]) {
                    if (j > n) break;
                    s -= vals[j] * 2;
                    vals[j] = -vals[j];
                }
            }
        }
        // cerr << its << endl;
        if (abs(s - k) <= d) {
            break;
        }
    }
    for (int p : large_primes) {
        if (s < k) {
            vals[p] = 1;
            ++s;
        } else {
            vals[p] = -1;
            --s;
        }
    }
    assert(s == k);
    vals.erase(vals.begin());
    cout << vals << '\n';
    // #ifdef HOUSE
    // cout.flush();
    // #endif
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    for (int i = 1; i < N; ++i) {
        for (auto [p, c] : sieve.get_prime_divs(i)) {
            if (c % 2 == 1) {
                where[p].pb(i);
            }
        }
    }

    int T;
    cin >> T;
    for (int test = 1; test <= T; ++test) {
        test_case(test);
    }

    return 0;
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 128ms
memory: 85848kb

input:

4
4 2
10 0
10 1
10 10

output:

1 1 -1 1 
1 -1 -1 1 -1 1 -1 -1 1 1 
-1
1 1 1 1 1 1 1 1 1 1

result:

ok ok (4 test cases)

Test #2:

score: -100
Runtime Error

input:

11475
1 0
1 1
2 0
2 1
2 2
3 0
3 1
3 2
3 3
4 0
4 1
4 2
4 3
4 4
5 0
5 1
5 2
5 3
5 4
5 5
6 0
6 1
6 2
6 3
6 4
6 5
6 6
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 7
8 0
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
9 0
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
10 0
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
11 0
11 1
11 2
11 3
11...

output:

result:
English 繁體中文 简体中文

服务器时间: 2024-12-05 08:45:24 | 开源项目