QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113868#6641. XOR DiceITMO_pengzoo#AC ✓4ms8948kbC++205.3kb2023-06-19 21:18:062023-06-19 21:18:08

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-19 21:18:08]
  • 评测
  • 测评结果:AC
  • 用时:4ms
  • 内存:8948kb
  • [2023-06-19 21:18:06]
  • 提交

answer

#include <bits/stdc++.h>
using  namespace std;

typedef long long ll;

const int mod = 998244353;
const int N = 100010;

vector<int> fact(N);
vector<int> ifact(N);

int add(int x, int y) {
    if (x + y >= mod) {
        return x + y - mod;
    }
    return x + y;
}

int mult(int x, int y) {
    return (int) ((x * 1LL * y) % mod);
}

int pow(int x, int p) {
    int ans = 1;
    while (p > 0) {
        if ((p & 1) == 1) {
            ans = mult(ans, x);
        }
        x = mult(x, x);
        p >>= 1;
    }
    return ans;
}

int inv(int x) {
    return pow(x, mod - 2);
}

int c_n_k(int n, int k) {
    if (n < k) {
        return 0;
    }
    return mult(fact[n], mult(ifact[k], ifact[n - k]));
}

//const int N = 1 << 17;
const int INF = 0x3f3f3f3f;

const ll lINF = 2e18;

int smin(int & x, int y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

ll smin(ll & x, ll y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

int smax(int & x, int y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

ll smax(ll & x, ll y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

class Node {
public:
    int mn, push;
    int l, r;

    Node() : mn(INF), push(0), l(-1), r(-1) {}

    Node(int _mn, int _l, int _r) : mn(_mn), push(0), l(_l), r(_r) {}

    Node operator+(const Node& other) const {
        return Node(std::min(mn, other.mn), l, other.r);
    }
};

class SegmentTree {
public:
    std::array<Node, 2 * N> tree;

    SegmentTree() {
        for (int i = 0; i < N; ++i) {
            tree[i + N] = Node(INF, i, i + 1);
        }
        for (int i = N - 1; i > 0; --i) {
            tree[i] = tree[i * 2] + tree[i * 2 + 1];
        }
    }

    void makePush(int v) {
        if (tree[v].push == 0) {
            return;
        }

        if (v < N) {
            tree[v * 2].push += tree[v].push;
            tree[v * 2 + 1].push += tree[v].push;
        }

        tree[v].mn += tree[v].push;
        tree[v].push = 0;
    }

    Node get(int v, int l, int r) {
        makePush(v);

        if (tree[v].r <= l || r <= tree[v].l) {
            return Node();
        }
        if (l <= tree[v].l && tree[v].r <= r) {
            return tree[v];
        }

        return get(v * 2, l, r) + get(v * 2 + 1, l, r);
    }

    void add(int v, int l, int r, int delta) {
        makePush(v);

        if (tree[v].r <= l || r <= tree[v].l) {
            return;
        }
        if (l <= tree[v].l && tree[v].r <= r) {
            tree[v].push += delta;
            makePush(v);
            return;
        }

        add(v * 2, l, r, delta);
        add(v * 2 + 1, l, r, delta);

        tree[v] = tree[v * 2] + tree[v * 2 + 1];
    }

    void set(int v, int pos, int val) {
        makePush(v);

        if (tree[v].l + 1 == tree[v].r) {
            tree[v].mn = val;
            return;
        }

        if (pos < tree[v * 2].r) {
            set(v * 2, pos, val);
            makePush(v * 2 + 1);
        } else {
            set(v * 2 + 1, pos, val);
            makePush(v * 2);
        }

        tree[v] = tree[v * 2] + tree[v * 2 + 1];
    }

    int get(int l, int r) {
        return get(1, l, r).mn;
    }

    void add(int l, int r, int delta) {
        add(1, l, r, delta);
    }

    void set(int pos, int val) {
        set(1, pos, val);
    }
};

vector <vector<int>> g(N), gr(N);
vector<bool> used;
vector<int> order, component;
vector<int> c(N);

void dfs1 (int v) {
    used[v] = true;
    for (int i = 0; i < (int) g[v].size(); ++i) {
        if (!used[g[v][i]]) {
            dfs1 (g[v][i]);
        }
    }
    order.push_back(v);
}

void dfs2 (int v, int col) {
    used[v] = true;
    component.push_back(v);
    c[v] = col;
    for (int i=0; i < (int) gr[v].size(); ++i) {
        if (!used[gr[v][i]]){
            dfs2 (gr[v][i], col);
        }
    }
}

vector<int> d;

int gcd0(int x, int y) {
    if (x == 0) {
        return y;
    }
    if (y == 0) {
        return x;
    }
    return gcd0(y, x % y);
}

int dfs3(int v, int gcd, int dist) {
    used[v] = true;
    d[v] = dist;
    component.push_back(v);
    for (int to : g[v]) {
        if (c[v] != c[to]) {
            continue;
        }
        if (!used[to]) {
            int gcd1 = dfs3(to, gcd, dist + 1);
            gcd = gcd0(gcd, gcd1);
        } else {
            int dl = abs(dist + 1 - d[to]);
            gcd = gcd0(gcd, dl);
        }
    }
    return gcd;
}

void solve() {
    int n, d;
    cin >> n >> d;
    for (int i = 0; i < n; ++i) {
        cout << 0 << " " << d << " " << 64 * d << " " << (64 + 1) * d << " " << 64 * 64 * d << " " << (64 * 64 + 1) * d << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
//    fact[0] = 1;
//    for (int i = 1; i < N; ++i) {
//        fact[i] = mult(i, fact[i - 1]);
//    }
//    ifact[N - 1] = inv(fact[N - 1]);
//    for (int i = N - 1; i > 0; --i) {
//        ifact[i - 1] = mult(i, ifact[i]);
//    }
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 2

output:

0 2 128 130 8192 8194
0 2 128 130 8192 8194
0 2 128 130 8192 8194

result:

ok Correct answer

Test #2:

score: 0
Accepted
time: 4ms
memory: 8736kb

input:

100 60

output:

0 60 3840 3900 245760 245820
0 60 3840 3900 245760 245820
0 60 3840 3900 245760 245820
0 60 3840 3900 245760 245820
0 60 3840 3900 245760 245820
0 60 3840 3900 245760 245820
0 60 3840 3900 245760 245820
0 60 3840 3900 245760 245820
0 60 3840 3900 245760 245820
0 60 3840 3900 245760 245820
0 60 3840 ...

result:

ok Correct answer

Test #3:

score: 0
Accepted
time: 4ms
memory: 8808kb

input:

99 2

output:

0 2 128 130 8192 8194
0 2 128 130 8192 8194
0 2 128 130 8192 8194
0 2 128 130 8192 8194
0 2 128 130 8192 8194
0 2 128 130 8192 8194
0 2 128 130 8192 8194
0 2 128 130 8192 8194
0 2 128 130 8192 8194
0 2 128 130 8192 8194
0 2 128 130 8192 8194
0 2 128 130 8192 8194
0 2 128 130 8192 8194
0 2 128 130 81...

result:

ok Correct answer

Test #4:

score: 0
Accepted
time: 1ms
memory: 8732kb

input:

99 59

output:

0 59 3776 3835 241664 241723
0 59 3776 3835 241664 241723
0 59 3776 3835 241664 241723
0 59 3776 3835 241664 241723
0 59 3776 3835 241664 241723
0 59 3776 3835 241664 241723
0 59 3776 3835 241664 241723
0 59 3776 3835 241664 241723
0 59 3776 3835 241664 241723
0 59 3776 3835 241664 241723
0 59 3776 ...

result:

ok Correct answer

Test #5:

score: 0
Accepted
time: 4ms
memory: 8664kb

input:

93 17

output:

0 17 1088 1105 69632 69649
0 17 1088 1105 69632 69649
0 17 1088 1105 69632 69649
0 17 1088 1105 69632 69649
0 17 1088 1105 69632 69649
0 17 1088 1105 69632 69649
0 17 1088 1105 69632 69649
0 17 1088 1105 69632 69649
0 17 1088 1105 69632 69649
0 17 1088 1105 69632 69649
0 17 1088 1105 69632 69649
0 1...

result:

ok Correct answer

Test #6:

score: 0
Accepted
time: 1ms
memory: 8948kb

input:

100 49

output:

0 49 3136 3185 200704 200753
0 49 3136 3185 200704 200753
0 49 3136 3185 200704 200753
0 49 3136 3185 200704 200753
0 49 3136 3185 200704 200753
0 49 3136 3185 200704 200753
0 49 3136 3185 200704 200753
0 49 3136 3185 200704 200753
0 49 3136 3185 200704 200753
0 49 3136 3185 200704 200753
0 49 3136 ...

result:

ok Correct answer

Test #7:

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

input:

100 5

output:

0 5 320 325 20480 20485
0 5 320 325 20480 20485
0 5 320 325 20480 20485
0 5 320 325 20480 20485
0 5 320 325 20480 20485
0 5 320 325 20480 20485
0 5 320 325 20480 20485
0 5 320 325 20480 20485
0 5 320 325 20480 20485
0 5 320 325 20480 20485
0 5 320 325 20480 20485
0 5 320 325 20480 20485
0 5 320 325 ...

result:

ok Correct answer

Test #8:

score: 0
Accepted
time: 3ms
memory: 8764kb

input:

1 57

output:

0 57 3648 3705 233472 233529

result:

ok Correct answer

Test #9:

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

input:

1 22

output:

0 22 1408 1430 90112 90134

result:

ok Correct answer

Test #10:

score: 0
Accepted
time: 3ms
memory: 8804kb

input:

1 60

output:

0 60 3840 3900 245760 245820

result:

ok Correct answer

Test #11:

score: 0
Accepted
time: 3ms
memory: 8780kb

input:

1 2

output:

0 2 128 130 8192 8194

result:

ok Correct answer

Test #12:

score: 0
Accepted
time: 3ms
memory: 8864kb

input:

10 24

output:

0 24 1536 1560 98304 98328
0 24 1536 1560 98304 98328
0 24 1536 1560 98304 98328
0 24 1536 1560 98304 98328
0 24 1536 1560 98304 98328
0 24 1536 1560 98304 98328
0 24 1536 1560 98304 98328
0 24 1536 1560 98304 98328
0 24 1536 1560 98304 98328
0 24 1536 1560 98304 98328

result:

ok Correct answer