QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #87689 | #5750. Siteswap | NYCU_Yamada | AC ✓ | 16ms | 5352kb | C++20 | 8.0kb | 2023-03-14 00:45:36 | 2023-03-14 00:45:38 |
Judging History
answer
#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA
tuple<int, int, int> brute(int N, vector<int> A) {
const int maxt = 1 << 20;
vector<int> vis(maxt, 0);
int cnt_o = 0, cnt_e = 0, cnt_b = 0;
for (int i = 0; i < maxt; ++i) {
if (vis[i] == 0b01) ++cnt_o;
if (vis[i] == 0b10) ++cnt_e;
if (vis[i] == 0b11) ++cnt_b;
if (i + A[i%N] < maxt) {
if (vis[i] == 0b01) --cnt_o;
if (vis[i] == 0b10) --cnt_e;
if (vis[i] == 0b11) --cnt_b;
vis[i+A[i%N]] = vis[i] | (1 << ((i+A[i%N])&1));
}
}
return {cnt_o, cnt_e, cnt_b};
}
void solve() {
int N; cin >> N;
vector<int> A(N);
for (int &x : A) cin >> x;
if (N % 2 == 1) {
for (int i = 0; i < N; ++i) A.eb(A[i]);
N *= 2;
}
// debug(brute(N, A));
int ans_o = 0, ans_e = 0, ans_b = 0;
vector<int> vis(N, 0);
for (int i = 0; i < N; ++i) {
if (vis[i]) continue;
int now = i, sum = 0, flag = (1 << (now&1));
do {
vis[now%N] = 1;
sum += A[now%N];
now += A[now%N];
flag |= (1 << (now&1));
} while (!vis[now%N]);
if (flag == 0b01) ans_o += sum / N;
if (flag == 0b10) ans_e += sum / N;
if (flag == 0b11) ans_b += sum / N;
}
cout << ans_o << " " << ans_e << " " << ans_b << "\n";
}
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;
#define int int64_t
#define double __float80
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())
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 <class F>
inline constexpr decltype(auto) lambda_fix(F&& f) {
return [f = std::forward<F>(f)](auto&&... args) {
return f(f, std::forward<decltype(args)>(args)...);
};
}
#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())
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 = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &);
template <size_t I = 0, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(const tuple<U...> &_t);
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &);
template <size_t I = 0, 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() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif
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;}
/// 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>) {
string _tmp_color = _color.back();
++_tmp_color[3], _color.emplace_back(_tmp_color);
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) {
string _tmp_color = _color.back();
++_tmp_color[3], _color.emplace_back(_tmp_color);
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) {
string _tmp_color = _color.back();
++_tmp_color[3], _color.emplace_back(_tmp_color);
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) {
string _tmp_color = _color.back();
++_tmp_color[3], _color.emplace_back(_tmp_color);
cerr << _color.back();
}
cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}
#endif
#endif
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3432kb
input:
3 3 1 5 0 6 4 6 4 0 4 0 2 6 4
output:
0 0 2 2 1 0 3 2 0
result:
ok 9 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3440kb
input:
100 10 94 8 4 52 7 53 16 96 29 1 10 23 35 96 34 86 39 16 72 63 96 10 51 2 46 21 15 31 41 28 42 83 10 75 67 64 88 46 98 3 17 14 98 10 24 77 54 48 16 37 23 88 99 84 10 52 93 44 87 84 80 37 22 73 28 10 35 80 96 60 75 19 100 63 54 88 10 38 49 63 68 29 67 3 57 68 48 10 89 57 51 21 61 16 100 73 99 83 10 6...
output:
2 0 34 0 0 56 0 0 36 0 0 57 4 0 51 0 13 47 25 14 28 0 0 49 10 0 55 0 0 30 9 0 48 0 0 48 15 11 22 0 7 34 9 0 39 4 7 26 9 0 56 6 10 49 6 5 32 0 0 45 7 4 44 8 0 46 7 4 60 24 19 0 0 0 57 0 13 28 9 1 37 0 0 58 7 0 38 0 0 40 6 6 21 3 9 31 3 10 51 7 9 28 19 10 39 0 3 51 22 8 29 0 8 40 7 0 51 0 0 40 0 16 45...
result:
ok 300 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 3404kb
input:
100 54 386 856 526 874 268 682 718 686 344 116 412 25 82 99 203 496 2 949 757 584 713 137 518 782 485 769 852 483 906 918 152 211 561 355 527 591 585 506 57 49 929 767 317 287 475 186 267 199 227 390 124 373 309 444 85 491 676 471 547 85 660 974 510 349 341 89 557 936 180 632 919 810 887 498 426 644...
output:
0 17 437 16 16 485 0 0 559 4 2 413 0 7 490 1 1 510 0 0 424 0 0 514 0 38 386 1 0 473 0 0 667 7 7 507 22 0 490 0 41 472 0 0 580 0 0 526 0 0 441 0 55 423 0 0 467 18 18 523 0 0 517 0 0 565 0 0 486 0 0 492 0 0 495 21 21 519 2 6 437 47 54 302 0 16 510 21 0 482 82 82 358 3 31 334 30 0 355 54 81 367 20 20 5...
result:
ok 300 numbers
Test #4:
score: 0
Accepted
time: 16ms
memory: 4636kb
input:
1 100000 173636392 284273077 698424898 5611435 902118118 237290573 833213168 776939793 5890016 899034976 776348831 518211565 717077869 409849809 602678259 232306557 142010208 148869327 319416709 814019507 368419097 599868858 338329488 88679485 555698506 294475578 715560768 893338866 371965797 381639...
output:
0 0 500204201
result:
ok 3 number(s): "0 0 500204201"
Test #5:
score: 0
Accepted
time: 14ms
memory: 5352kb
input:
2 27355 460071504 378603706 534707902 580629932 984454706 47518920 863592507 534539132 32710375 333680435 834350586 804715694 851485226 611532912 367032640 220290347 971674730 390231297 220133525 423772279 762042987 778306763 418668366 841875081 59148109 99723573 442421595 652768507 141655948 405219...
output:
0 0 501084219 5102 5102 500096109
result:
ok 6 numbers