QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#106854 | #6371. Half is Good | ckiseki# | TL | 1136ms | 59752kb | C++20 | 3.2kb | 2023-05-19 15:55:31 | 2023-05-19 15:55:33 |
Judging History
answer
#include <bits/stdc++.h>
#ifdef CKISEKI
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
using std::cerr;
template <typename ...T>
void debug_(const char *s, T ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int cnt = sizeof...(T);
(..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
cerr << "\e[1;32m[ " << s << " ] = [ ";
for (int f = 0; L != R; ++L)
cerr << (f++ ? ", " : "") << *L;
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif
#define all(v) begin(v),end(v)
using namespace std;
const int maxn = 10000025;
const int SHIFT = 22;
const int maxc = 1 << SHIFT;
const int mask = (1 << SHIFT) - 1;
int pa[maxn];
int label[maxn];
int rk[maxn];
int perm[maxn];
unsigned ans[maxn >> 5];
int cnt[maxc];
unsigned getNext(unsigned &s) {
s = s ^ (s << 13);
s = s ^ (s >> 17);
s = s ^ (s << 5);
return s;
}
int anc(int x) {
return pa[x]<0 ? x : pa[x]=anc(pa[x]);
}
bool join(int x, int y) {
x = anc(x);
y = anc(y);
if (x == y) return false;
if (pa[x] > pa[y])
swap(x, y);
debug(pa[x], pa[y]);
int nrk = (pa[x]==pa[y] ? pa[x]-1 : pa[x]);
pa[y] = x;
pa[x] = nrk;
return true;
}
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n, m;
unsigned init_s;
cin >> n >> m >> init_s;
int shift = 0;
for (int i = 0; i < m; i++)
rk[i] = i;
for (int i = 0; i < m; i++)
perm[i] = i;
for (int t = 0; t < 3; t++) {
unsigned s = init_s;
for (int i = 0; i < m; i++) {
int u = getNext(s);
int v = getNext(s);
long long w = getNext(s) / 4;
w *= getNext(s);
label[i] = w >> shift & mask;
}
orange(perm, perm + m);
orange(label, label + m);
for (int i = 0; i < maxc; i++)
cnt[i] = 0;
for (int i = 0; i < m; i++)
++cnt[label[i]];
for (int i = 1; i < maxc; i++)
cnt[i] += cnt[i - 1];
for (int i = m - 1; i >= 0; i--) {
rk[perm[i]] = --cnt[label[perm[i]]];
}
for (int i = 0; i < m; i++)
perm[rk[i]] = i;
orange(rk, rk + m);
orange(perm, perm + m);
shift += SHIFT;
}
// DSU init
for (int i = 0; i < n; i++)
pa[i] = -1;
int *edge_u = rk;
int *edge_v = label;
// vector<long long> edge_w(m);
unsigned s = init_s;
for (int i = 0; i < m; i++) {
int u = getNext(s) % n;
int v = getNext(s) % n;
long long w = getNext(s) / 4;
w *= getNext(s);
edge_u[i] = u;
edge_v[i] = v;
// edge_w[i] = w;
debug(u, v, w);
}
for (int i = 0; i < m; i++) {
int p = perm[i];
// debug(edge_u[p], edge_v[p], edge_w[p]);
if (join(edge_u[p], edge_v[p])) {
ans[p >> 5] |= 1u << (p % 32);
}
}
const int L = (m + 31) / 32;
for (int i = 0; i < L; i++) {
debug(bitset<32>(ans[i]));
cout << ans[i] << (i+1==L ? '\n' : ' ');
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 10ms
memory: 28564kb
input:
4 7 47
output:
72
result:
ok you found 2 edges (out of 2 edges)
Test #2:
score: 0
Accepted
time: 8ms
memory: 27788kb
input:
1 1 956091059
output:
0
result:
ok you found 0 edges (out of 0 edges)
Test #3:
score: 0
Accepted
time: 8ms
memory: 27684kb
input:
1 10 675265052
output:
0
result:
ok you found 0 edges (out of 0 edges)
Test #4:
score: 0
Accepted
time: 10ms
memory: 29288kb
input:
1 100 649558818
output:
0 0 0 0
result:
ok you found 0 edges (out of 0 edges)
Test #5:
score: 0
Accepted
time: 2ms
memory: 28316kb
input:
1 300 796656507
output:
0 0 0 0 0 0 0 0 0 0
result:
ok you found 0 edges (out of 0 edges)
Test #6:
score: 0
Accepted
time: 3ms
memory: 28004kb
input:
1 1000 570935698
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok you found 0 edges (out of 0 edges)
Test #7:
score: 0
Accepted
time: 12ms
memory: 27748kb
input:
1 5000 374761337
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok you found 0 edges (out of 0 edges)
Test #8:
score: 0
Accepted
time: 8ms
memory: 29416kb
input:
1 10000 705177612
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok you found 0 edges (out of 0 edges)
Test #9:
score: 0
Accepted
time: 17ms
memory: 29068kb
input:
1 100000 900413157
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok you found 0 edges (out of 0 edges)
Test #10:
score: 0
Accepted
time: 41ms
memory: 29080kb
input:
1 300000 347539594
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok you found 0 edges (out of 0 edges)
Test #11:
score: 0
Accepted
time: 220ms
memory: 41068kb
input:
1 1000000 659451863
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok you found 0 edges (out of 0 edges)
Test #12:
score: 0
Accepted
time: 1136ms
memory: 59752kb
input:
1 3000000 415743523
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok you found 0 edges (out of 0 edges)
Test #13:
score: -100
Time Limit Exceeded
input:
1 8000000 99180511