QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#113868 | #6641. XOR Dice | ITMO_pengzoo# | AC ✓ | 4ms | 8948kb | C++20 | 5.3kb | 2023-06-19 21:18:06 | 2023-06-19 21:18:08 |
Judging History
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