QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#217773 | #5024. 【模板】双端队列 | Xiaohuba | 0 | 1ms | 3808kb | C++14 | 5.4kb | 2023-10-17 12:27:23 | 2023-10-17 12:27:24 |
answer
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#if __cplusplus < 201400
#warning "Please use c++14 or higher."
#define INLINE_V
#define REGISTER_V register
#define CPP14CONSTEXPR
#define gcd __gcd
#define CPP14ENABLE_IF
#elif __cplusplus < 201700
#define INLINE_V
#define REGISTER_V
#define CPP14CONSTEXPR constexpr
#define gcd __gcd
#define CPP14ENABLE_IF ,enable_if_t<_is_integer<T>, int> = 0
#else
#define INLINE_V inline
#define REGISTER_V
#define CPP14CONSTEXPR constexpr
#define CPP14ENABLE_IF ,enable_if_t<_is_integer<T>, int> = 0
#endif
#if !defined(_WIN32) && !defined(LOCK_GETCHAR)
#define getchar getchar_unlocked
#endif
#define il inline
#define mkp make_pair
#define fi first
#define se second
#define For(i,j,k) for(REGISTER_V int i=(j);i<=(k);++i) // NOLINT
#define ForDown(i,j,k) for(REGISTER_V int i=(j);i>=(k);--i) // NOLINT
#define pb push_back
#define eb emplace_back
#define FileIO(filename) freopen(filename".in","r",stdin);freopen(filename".out","w",stdout)
using ll = long long;
using lll = __int128_t;
using uint = unsigned int;
using ull = unsigned long long;
using ulll = __uint128_t;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#if __cplusplus >= 201400
template <class T> INLINE_V constexpr bool _is_integer = numeric_limits<T>::is_integer;
template <> INLINE_V constexpr bool _is_integer<__int128> = true;
template <> INLINE_V constexpr bool _is_integer<__uint128_t> = true;
template <> INLINE_V constexpr bool _is_integer<bool> = false;
template <> INLINE_V constexpr bool _is_integer<char> = false;
template <class T CPP14ENABLE_IF>
INLINE_V constexpr T INF = numeric_limits<T>::max() >> 1;
#endif
template<typename T> constexpr il T sq(const T & x){return x*x;}
template<typename T> CPP14CONSTEXPR il T cmin(T & x, const T &y){x=min(x,y);}
template<typename T> CPP14CONSTEXPR il T cmax(T & x, const T &y){x=max(x,y);}
template<typename T> CPP14CONSTEXPR il T qpow(T x, ull y, T mod){T ans=1;x%=mod;while(y){if(y&1)(ans*=x)%=mod;(x*=x)%=mod;y>>=1;}return ans;}
template<typename T> CPP14CONSTEXPR il T qpow(T x, ull y){T ans=1;while(y){if(y&1)ans*=x;x*=x;y>>=1;}return ans;}
template<typename T CPP14ENABLE_IF> il void read(T &x){ x=0;int f=1;int c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=f;}
template<typename T, typename ... Args> il void read(T &x, Args &... y){ read(x);read(y...); }
// File head end
// clang-format on
namespace {
constexpr ll MAXN = 205;
int T, n, a[MAXN];
bool f[MAXN][MAXN][8];
il void solve() {
read(n);
For(i, 1, n) read(a[i]);
memset(f, 0, sizeof(f));
For(i, 1, n) {
if (a[i])
f[i][i][2] = f[i][i][6] = 1;
else
f[i][i][0] = f[i][i][4] = 1;
}
For(len, 2, n) For(i, 1, n - len + 1) {
int j = i + len - 1;
if (a[i]) {
if (f[i + 1][j][4]) {
f[i][j][2] = 1;
} else if (f[i + 1][j][6] || f[i + 1][j][5]) {
f[i][j][0] = f[i + 1][j][6];
f[i][j][3] = f[i + 1][j][5];
} else if (f[i + 1][j][7]) {
f[i][j][1] = 1;
}
if (f[i + 1][j][0]) {
f[i][j][5] = 1;
} else if (f[i + 1][j][2] || f[i + 1][j][1]) {
f[i][j][4] = f[i + 1][j][1];
f[i][j][7] = f[i + 1][j][2];
} else if (f[i + 1][j][3]) {
f[i][j][6] = 1;
}
} else {
if (f[i + 1][j][6]) {
f[i][j][2] = 1;
} else if (f[i + 1][j][7] || f[i + 1][j][4]) {
f[i][j][0] = f[i + 1][j][4];
f[i][j][3] = f[i + 1][j][7];
} else if (f[i + 1][j][5]) {
f[i][j][1] = 1;
}
if (f[i + 1][j][1]) {
f[i][j][5] = 1;
} else if (f[i + 1][j][3] || f[i + 1][j][0]) {
f[i][j][4] = f[i + 1][j][0];
f[i][j][7] = f[i + 1][j][3];
} else if (f[i + 1][j][2]) {
f[i][j][6] = 1;
}
}
if (a[j]) {
if (f[i][j - 1][4]) {
f[i][j][2] = 1;
} else if (f[i][j - 1][6] || f[i][j - 1][5]) {
f[i][j][0] = f[i][j - 1][6];
f[i][j][3] = f[i][j - 1][5];
} else if (f[i][j - 1][7]) {
f[i][j][1] = 1;
}
if (f[i][j - 1][0]) {
f[i][j][5] = 1;
} else if (f[i][j - 1][2] || f[i][j - 1][1]) {
f[i][j][4] = f[i][j - 1][1];
f[i][j][7] = f[i][j - 1][2];
} else if (f[i][j - 1][3]) {
f[i][j][6] = 1;
}
} else {
if (f[i][j - 1][6]) {
f[i][j][2] = 1;
} else if (f[i][j - 1][7] || f[i][j - 1][4]) {
f[i][j][0] = f[i][j - 1][4];
f[i][j][3] = f[i][j - 1][7];
} else if (f[i][j - 1][5]) {
f[i][j][1] = 1;
}
if (f[i][j - 1][1]) {
f[i][j][5] = 1;
} else if (f[i][j - 1][3] || f[i][j - 1][0]) {
f[i][j][4] = f[i][j - 1][0];
f[i][j][7] = f[i][j - 1][3];
} else if (f[i][j - 1][2]) {
f[i][j][6] = 1;
}
}
if (f[i][j][2])
f[i][j][3] = 0;
if (f[i][j][0])
f[i][j][1] = 0;
if (f[i][j][5])
f[i][j][7] = 0;
if (f[i][j][4])
f[i][j][6] = 0;
}
if (f[1][n][2])
puts("First");
else if (f[1][n][1])
puts("Second");
else if (f[1][n][0] || f[1][n][3])
puts("Draw");
else
assert(0);
}
il void solver_main() {
read(T);
while (T--)
solve();
}
} // namespace
signed main() { return solver_main(), 0; }
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3808kb
input:
40 15 1042186166 1065050038 1052442342 117744385 1044381358 996146407 947617159 1031691934 27328777 130294601 1065311743 1065082111 12845136 941620871 1042177446 15 1068465534 15766217 69219008 95461385 1048542590 1051709438 1048575351 1072652151 978275647 1044381687 999247358 1062194999 1054829887 ...
output:
Second Second Second Second Second Second Second Second Second Draw Draw Second Second Second Second Second Second Second Second Second Second Second Second Second Draw Second Second Second Draw Second Second Second Second Second Second Second Second Second Second Draw
result:
wrong answer 4th words differ - expected: 'First', found: 'Second'
Subtask #2:
score: 0
Runtime Error
Test #2:
score: 0
Runtime Error
input:
40 987 1073733087 9437225 570431533 1031755263 1031755251 579873284 571521061 536872960 546353705 43000364 535780827 1065313790 536834043 41953824 503270871 1040175099 8426021 537960961 1054732 545292837 34648585 34603052 546314244 537965060 9439748 41953292 43037189 9447949 536864767 1073698294 503...
output:
result:
Subtask #3:
score: 0
Runtime Error
Test #4:
score: 0
Runtime Error
input:
40 49999 30704571 23631198 10459697 452884 909025 3745220 5633170 29257098 24428644 21991837 21100897 21249665 18667093 13809790 21220831 32750672 29531337 31709216 17139349 4444339 787544 14509794 3855820 201034 13281440 26541636 31476242 10318360 20485824 26793325 8264891 22349828 20554718 7556006...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #6:
score: 0
Runtime Error
input:
40 49035 1073176430 531291499 1005508607 675350672 368768 867368831 139504132 1321089 134482448 464248170 1068169195 68946580 469491567 738764816 742459920 535197167 531887598 672172545 609558673 608209040 335282031 532674543 72878741 610117777 138447508 398155759 71608464 672172165 402325355 609845...