QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #798102 | #699. Gaggle | SorahISA | AC ✓ | 440ms | 34480kb | C++23 | 11.5kb | 2024-12-04 04:48:06 | 2024-12-04 04:48:07 |
Judging History
answer
#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA
struct DSU {
vector<int> p;
int maxn;
void init(int N) {
maxn = N + 1;
p.resize(maxn), iota(ALL(p), 0);
}
int R(int x) { return x ^ p[x] ? p[x] = R(p[x]) : x; }
int U(int x, int y) { return (x = R(x)) ^ (y = R(y)) ? p[x] = y, 1 : 0; }
};
void solve() {
int N; cin >> N;
vector<int> A(N);
for (int &x : A) cin >> x, --x;
DSU dsu; dsu.init(N);
set<int> can_in;
for (int i = 0; i < N; ++i) can_in.ee(i);
for (int i = 0; i < N-1; ++i) {
if (dsu.R(i) == dsu.R(A[i]) or not can_in.contains(A[i])) {
int x1 = *begin(can_in);
int x2 = *next(begin(can_in));
A[i] = (dsu.R(i) != dsu.R(x1) ? x1 : x2);
}
can_in.erase(A[i]), dsu.U(i, A[i]);
}
A[N-1] = *begin(can_in);
for (int &x : A) ++x;
print(A);
}
int32_t main() {
fastIO();
int t = 1; // cin >> t;
for (int _ = 1; _ <= t; ++_) {
// cout << "Case #" << _ << ": ";
solve();
}
return 0;
}
#else
#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #include <bits/extc++.h>
// #include <tr2/dynamic_bitset>
using i64 = long long;
using i128 = __int128;
#define int i64
using f80 = long double;
using f128 = __float128;
#define double f80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;
// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())
#define popcnt(x) __builtin_popcountll(x)
// template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> {
// static_assert(D >= 1, "Vector dimension must be greater than zero!");
// template <typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(args...)) {}
// };
// template <typename T> struct Vec<1, T> : vector<T> {
// Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
// };
template <typename T> ostream& operator << (ostream &os, const vector<T> &vec)
{ for (size_t i = 0; i < size(vec); ++i) { if (i) os << " "; os << vec[i]; } return os; }
#ifdef local
#define fastIO() void()
#define debug(...) \
_color.emplace_back("\u001b[31m"), \
fprintf(stderr, "%sAt [%s], line %d: (%s) = ", _color.back().c_str(), __FUNCTION__, __LINE__, #__VA_ARGS__), \
_do(__VA_ARGS__), _color.pop_back(), \
fprintf(stderr, "%s", _color.back().c_str())
#define print(...) \
fprintf(stdout, "%s", "\u001b[36m"), \
_P(__VA_ARGS__), \
fprintf(stdout, "%s", "\u001b[0m")
deque<string> _color{"\u001b[0m"};
template <typename T> concept is_string = is_same_v<T, string&> or is_same_v<T, const string&>;
template <typename T> concept is_iterable = requires (T _t) { begin(_t); };
template <typename T> inline void _print_err(T &&_t);
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(const tuple<U...> &_t);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(tuple<U...> &_t);
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu);
inline void _do() { cerr << "\n"; }
template <typename T> inline void _do(T &&_t) { _print_err(_t), cerr << "\n"; }
template <typename T, typename ...U> inline void _do(T &&_t, U &&..._u) { _print_err(_t), cerr << ", ", _do(_u...); }
#else
#define fastIO() cin.tie(0)->sync_with_stdio(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#endif
inline void _P() { cout << "\n"; }
template <typename T> inline void _P(T &&_t) { cout << _t << "\n"; }
template <typename T, typename ...U> inline void _P(T &&_t, U &&..._u) { cout << _t << " ", _P(_u...); }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int getRand(int L, int R) {
if (L > R) swap(L, R);
return (int)(rng() % ((uint64_t)R - L + 1) + L);
}
template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }
template <typename T> void make_unique(vector<T> &vec) {
if (not is_sorted(ALL(vec))) sort(ALL(vec));
vec.erase(unique(ALL(vec)), end(vec));
}
/// below are Fast I/O and _print_err templates ///
/*
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
#include <unistd.h>
const int S = 65536;
int OP = 0;
char OB[S];
inline char RC() {
static char buf[S], *p = buf, *q = buf;
return p == q and (q = (p = buf) + read(0, buf, S)) == buf ? -1 : *p++;
}
inline int RI() {
static char c;
int a;
while (((c = RC()) < '0' or c > '9') and c != '-' and c != -1);
if (c == '-') {
a = 0;
while ((c = RC()) >= '0' and c <= '9') a *= 10, a -= c ^ '0';
}
else {
a = c ^ '0';
while ((c = RC()) >= '0' and c <= '9') a *= 10, a += c ^ '0';
}
return a;
}
inline void WI(int n, char c = '\n') {
static char buf[20], p;
if (n == 0) OB[OP++] = '0';
p = 0;
if (n < 0) {
OB[OP++] = '-';
while (n) buf[p++] = '0' - (n % 10), n /= 10;
}
else {
while (n) buf[p++] = '0' + (n % 10), n /= 10;
}
for (--p; p >= 0; --p) OB[OP++] = buf[p];
OB[OP++] = c;
if (OP > S-20) write(1, OB, OP), OP = 0;
}
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
*/
#ifdef local
template <typename T> inline void _print_err(T &&_t) { cerr << _t; }
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back() << "[";
for (bool _first = true; auto &_x : _t) {
if (!_first) cerr << ", ";
_print_err(_x), _first = false;
}
cerr << "]" << (_color.pop_back(), _color.back());
}
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back() << "(";
_print_err(_tu.first), cerr << ", ", _print_err(_tu.second);
cerr << ")" << (_color.pop_back(), _color.back());
return os;
}
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &) {
cerr << ")" << (_color.pop_back(), _color.back());
}
template <size_t I = 0, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(const tuple<U...> &_t) {
if (!I) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back();
}
cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &) {
cerr << ")" << (_color.pop_back(), _color.back());
}
template <size_t I = 0, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(tuple<U...> &_t) {
if (!I) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back();
}
cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}
#endif
#endif
/**
*
*
*
* iiiiii iiiiiiiiii iiiiiiiiiiiiii
* iiiiiiiiiiiii iiiiiii iiii iiiiiiiiiiiiiii ii iiii
* iiiiiiii iiiiiiiii iiii iiii iii iii iiiiiiiiii
* iiiiiii iiiiii iiii iiii ii iiiiiiiiii iiii iiii
* iiiiii iiiii iiii iiii iii iiii iiiiiiiiiiiiiiiii ii
* iiiiii iiiiiii iiiiiii iiiiiiii iii iiiiiiiiiiiiii iii iiii
* iiiiii iiiiiii iiiii ii iiii iiiiiiiiiii iiii iii iiii iiii iii
* iiiii iiiiiiii ii iiiii iiii iiiiiiiii iii iii iii iii ii iiii
* iiiiii iiiiiiii iiiii iiiii iiiiiiiiiiiiiiii iii iii ii iii iii iiii
* iiiii iiiiii iiii iiiiii iiiiiii iii iii iiii ii i ii iii iii
* iiiiii iiii iiiiiiiiiiiiiii iii iiii iiiii iii ii iii iii ii
* iiiii iiiiiiii iiiiiiiiii iiii iiiiiiiii ii iii ii
* iiiii iiiiii iiii iiiii iii ii ii i
* iiiiii iiiiiiii iiiii iiiii ii ii ii
* iiiii iiii iiii iiiiiiiiiiii ii
* iii iiii iiii iiiiiiii
* iiiii iiii
* iiii iiii
* iiii iiiii
* iii iiiii
* iii iiiii
* iii iiiiii
* iiiiiiiii
* iiiiii
*
*
*
**/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3684kb
input:
4 2 1 4 3
output:
2 3 4 1
result:
ok single line: '2 3 4 1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
3 3 3 1
output:
3 1 2
result:
ok single line: '3 1 2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
10 3 5 2 6 4 9 1 10 8 7
output:
3 5 2 6 4 9 1 10 8 7
result:
ok single line: '3 5 2 6 4 9 1 10 8 7'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
10 6 1 1 1 1 1 1 1 1 1
output:
6 1 2 3 4 7 8 9 10 5
result:
ok single line: '6 1 2 3 4 7 8 9 10 5'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
10 3 9 1 8 7 10 5 4 2 6
output:
3 9 2 8 7 10 1 5 6 4
result:
ok single line: '3 9 2 8 7 10 1 5 6 4'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
10 10 3 8 5 7 4 9 1 6 2
output:
10 3 8 5 7 4 9 1 2 6
result:
ok single line: '10 3 8 5 7 4 9 1 2 6'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
14 4 10 10 13 3 5 13 6 13 8 1 9 1 3
output:
4 10 1 13 3 5 2 6 7 8 9 11 14 12
result:
ok single line: '4 10 1 13 3 5 2 6 7 8 9 11 14 12'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
20 13 11 13 14 1 11 20 7 1 4 4 15 10 13 16 17 12 6 12 3
output:
13 11 1 14 2 3 20 7 4 5 6 15 8 10 16 17 9 12 18 19
result:
ok single line: '13 11 1 14 2 3 20 7 4 5 6 15 8 10 16 17 9 12 18 19'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
18 4 6 9 7 9 14 14 2 5 12 13 5 14 9 17 3 10 4
output:
4 6 9 7 1 14 2 3 5 12 13 8 10 15 17 11 18 16
result:
ok single line: '4 6 9 7 1 14 2 3 5 12 13 8 10 15 17 11 18 16'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
7 3 1 4 1 4 2 1
output:
3 1 4 5 6 7 2
result:
ok single line: '3 1 4 5 6 7 2'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
14 13 8 10 13 1 10 11 4 12 5 13 8 7 3
output:
13 8 10 1 2 3 11 4 12 5 6 7 14 9
result:
ok single line: '13 8 10 1 2 3 11 4 12 5 6 7 14 9'
Test #12:
score: 0
Accepted
time: 420ms
memory: 34412kb
input:
500000 158419 146468 301468 344333 90332 9218 208387 131963 254206 176564 428626 145087 454883 243071 470404 47393 107060 468705 37237 483563 234972 14702 199167 40802 366980 360763 15141 38430 211994 261984 470706 273908 200979 92664 94293 174050 482925 65603 135546 270981 94944 416372 27332 303331...
output:
158419 146468 301468 344333 90332 9218 208387 131963 254206 176564 428626 145087 454883 243071 470404 47393 107060 468705 37237 483563 234972 14702 199167 40802 366980 360763 15141 38430 211994 261984 470706 273908 200979 92664 94293 174050 482925 65603 135546 270981 94944 416372 27332 303331 337384...
result:
ok single line: '158419 146468 301468 344333 90...021 121942 408942 313585 288451'
Test #13:
score: 0
Accepted
time: 412ms
memory: 34468kb
input:
500000 477232 329885 326019 101234 281842 334975 418262 24517 192513 413073 474138 328053 184414 444689 499524 393567 243285 76099 172515 61951 69005 293592 155008 277593 25270 106477 323093 300930 235135 430010 47540 44437 372262 324792 281072 331172 233691 249816 471653 126494 48958 164189 99092 3...
output:
477232 329885 326019 101234 281842 334975 418262 24517 192513 413073 474138 328053 184414 444689 499524 393567 243285 76099 172515 61951 69005 293592 155008 277593 25270 106477 323093 300930 235135 430010 47540 44437 372262 324792 281072 331172 233691 249816 471653 126494 48958 164189 99092 310296 9...
result:
ok single line: '477232 329885 326019 101234 28...308 491531 493094 496007 491820'
Test #14:
score: 0
Accepted
time: 174ms
memory: 34400kb
input:
500000 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859 50859...
output:
50859 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...
result:
ok single line: '50859 1 2 3 4 5 6 7 8 9 10 11 ...997 499998 499999 500000 297689'
Test #15:
score: 0
Accepted
time: 440ms
memory: 34388kb
input:
500000 222822 374812 479503 383228 47095 307693 125084 424747 289836 415373 427156 10175 446881 242393 421522 437860 393194 447985 93601 199001 486351 314498 471274 279964 105289 271171 140372 25856 60700 351380 358619 327481 117244 229530 423177 297004 123555 264272 50112 356760 447246 147764 22276...
output:
222822 374812 479503 383228 47095 307693 125084 424747 289836 415373 427156 10175 446881 242393 421522 437860 393194 447985 93601 199001 486351 314498 471274 279964 105289 271171 140372 25856 60700 351380 358619 327481 117244 229530 423177 297004 123555 264272 50112 356760 447246 147764 222765 768 3...
result:
ok single line: '222822 374812 479503 383228 47...349 376847 393767 424061 431209'
Test #16:
score: 0
Accepted
time: 304ms
memory: 34480kb
input:
500000 35493 249111 376615 429653 316426 262755 268577 440625 130977 358171 390862 251761 456874 111962 11835 352631 72501 229154 399628 441105 455130 334637 380952 204811 234092 242671 317229 467338 212193 123091 135421 471418 320537 420295 426709 159417 280051 163366 342620 440668 302953 490389 15...
output:
35493 249111 376615 429653 316426 262755 268577 440625 130977 358171 390862 251761 456874 111962 11835 352631 72501 229154 399628 441105 455130 334637 380952 204811 234092 242671 317229 467338 212193 123091 135421 471418 320537 420295 426709 159417 280051 163366 342620 440668 302953 490389 152642 35...
result:
ok single line: '35493 249111 376615 429653 316...606 498687 499628 499219 499743'
Test #17:
score: 0
Accepted
time: 215ms
memory: 23412kb
input:
324170 203320 3061 205420 191113 297734 212569 283759 253353 111669 200085 291163 136982 241358 303217 129991 184618 7606 285879 208036 165083 236469 156468 312449 217747 105029 96046 43048 206970 136494 99905 149 118575 304483 25797 85368 232256 277272 2464 144496 278544 230170 211045 189667 103991...
output:
203320 3061 205420 191113 297734 212569 283759 253353 111669 200085 291163 136982 241358 303217 129991 184618 7606 285879 208036 165083 236469 156468 312449 217747 105029 96046 43048 206970 136494 99905 149 118575 304483 25797 85368 232256 277272 2464 144496 278544 230170 211045 189667 103991 253159...
result:
ok single line: '203320 3061 205420 191113 2977...156 324160 324159 324168 324162'
Test #18:
score: 0
Accepted
time: 359ms
memory: 30572kb
input:
437814 129124 359145 303968 306572 2162 134635 154564 254855 294651 245551 356404 325872 79540 194644 355619 154339 10660 223560 224425 288595 294469 297325 140499 428706 153913 72027 122571 328305 63724 358465 412860 181329 153490 148267 328064 290439 124583 49598 331164 119457 299919 71504 139428 ...
output:
129124 359145 303968 306572 2162 134635 154564 254855 294651 245551 356404 325872 79540 194644 355619 154339 10660 223560 224425 288595 294469 297325 140499 428706 153913 72027 122571 328305 63724 358465 412860 181329 153490 148267 328064 290439 124583 49598 331164 119457 299919 71504 139428 343949 ...
result:
ok single line: '129124 359145 303968 306572 21...328 391031 309913 346237 401724'
Test #19:
score: 0
Accepted
time: 31ms
memory: 7076kb
input:
61963 26077 23336 4384 53641 585 16639 61011 21912 60691 24797 25502 59260 43619 42577 45114 36789 45138 1083 44619 51365 14749 36733 2970 30754 9924 48794 53023 4155 9945 51731 15904 44439 48442 32820 58591 58542 29910 42816 17589 56859 27037 22619 54230 59251 55133 2002 45231 25862 6932 43335 5179...
output:
26077 23336 4384 53641 585 16639 61011 21912 60691 24797 25502 59260 43619 42577 45114 36789 45138 1083 44619 51365 14749 36733 2970 30754 9924 48794 53023 4155 9945 51731 15904 44439 48442 32820 58591 58542 29910 42816 17589 56859 27037 22619 54230 59251 55133 2002 45231 25862 6932 43335 51797 4101...
result:
ok single line: '26077 23336 4384 53641 585 166...2 61942 61948 61953 61957 61955'
Test #20:
score: 0
Accepted
time: 237ms
memory: 25256kb
input:
354479 46571 107759 97656 309656 237652 350008 1237 73616 143057 223999 299254 158855 165336 342898 316262 119574 350701 328517 22700 270837 64364 28857 305294 121783 32762 252469 249083 33814 247756 147697 32124 307454 7994 329455 155358 151513 353922 336534 82105 148025 104717 97346 168570 51998 1...
output:
46571 107759 97656 309656 237652 350008 1237 73616 143057 223999 299254 158855 165336 342898 316262 119574 350701 328517 22700 270837 64364 28857 305294 121783 32762 252469 249083 33814 247756 147697 32124 307454 7994 329455 155358 151513 353922 336534 82105 148025 104717 97346 168570 51998 156074 1...
result:
ok single line: '46571 107759 97656 309656 2376...416 354461 354470 354450 354478'
Test #21:
score: 0
Accepted
time: 171ms
memory: 20740kb
input:
278978 12200 26770 27701 143372 113481 59298 42008 22628 171402 47570 97297 240117 105271 44426 24101 64007 82828 207228 269426 201801 63962 118130 17499 120273 152728 37947 258267 71156 16231 259089 228885 146167 262285 216734 19812 153319 193817 60405 264146 148462 261534 45542 176575 157817 25121...
output:
12200 26770 27701 143372 113481 59298 42008 22628 171402 47570 97297 240117 105271 44426 24101 64007 82828 207228 269426 201801 63962 118130 17499 120273 152728 37947 258267 71156 16231 259089 228885 146167 262285 216734 19812 153319 193817 60405 264146 148462 261534 45542 176575 157817 251218 87007...
result:
ok single line: '12200 26770 27701 143372 11348...965 278969 278974 278975 278976'