QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#34741 | #4251. Game | dutinmeow# | 2 | 1ms | 3956kb | C++20 | 10.2kb | 2022-06-12 06:37:26 | 2024-05-26 00:52:50 |
Judging History
answer
#include "game.h"
#define NDEBUG
#include <bits/stdc++.h>
using namespace std;
#pragma region debug
#ifndef NDEBUG
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
return os << '(' << p.first << ", " << p.second << ')';
}
template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &p) {
return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ')';
}
template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &p) {
return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ", " << get<3>(p) << ')';
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
os << '[';
if (v.size()) {
os << *v.begin();
for (auto i = next(v.begin()); i != v.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, const deque<T> &d) {
os << '[';
if (d.size()) {
os << *d.begin();
for (auto i = next(d.begin()); i != d.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, stack<T> s) {
os << '[';
if (s.size()) {
int n = s.size();
vector<T> v(n);
for (int i = 0; i < n; i++) {
v[i] = s.top();
s.pop();
}
os << v[n - 1];
for (int i = n - 2; i >= 0; i--)
os << ", " << v[i];
}
return os << "]>";
}
template<typename T>
ostream &operator<<(ostream &os, queue<T> q) {
os << '[';
if (q.size()) {
int n = q.size();
vector<T> v(n);
for (int i = 0; i < n; i++) {
v[i] = q.front();
q.pop();
}
os << v[n - 1];
for (int i = n - 2; i >= 0; i--)
os << ", " << v[i];
}
return os << "]>";
}
template<typename T, size_t N>
ostream &operator<<(ostream &os, const array<T, N> &a) {
os << '[';
if (N) {
os << *a.begin();
for (auto i = next(a.begin()); i != a.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, const set<T> &s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = next(s.begin()); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = next(s.begin()); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = next(s.begin()); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &m) {
os << '[';
if (m.size()) {
os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
for (auto i = next(m.begin()); i != m.end(); i++)
os << ", " << '(' << i->first << " : " << i->second << ')';
}
return os << ']';
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const unordered_map<T1, T2> &m) {
os << '[';
if (m.size()) {
os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
for (auto i = next(m.begin()); i != m.end(); i++)
os << ", " << '(' << i->first << " : " << i->second << ')';
}
return os << ']';
}
map<char, string> _dbg_dict {
{'1', "--------------------------------"},
{'2', "================================"},
{'3', "≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡"},
{'4', "################################"},
{'*', "********************************"},
{'_', "_"},
{'<', "<!---- "},
{'>', " ----!>"},
{'(', "(!==== "},
{')', "==== !)"},
{'[', "[!≡≡≡≡ "},
{']', " ≡≡≡≡!]"},
{'{', "{!#### "},
{'}', " ####!}"},
{'c', "checkpoint "},
{'l', "line "},
{'n', "\n"},
{'t', "\t"}
};
template<typename T>
void _dbg_print(string var, const T &a) { cerr << var << " = " << a << '\n'; }
void _dbg_print(string var, const char *a) {
int n = strlen(a);
for (int i = 0; i < n; i++)
cerr << (i < n - 1 && a[i] == '_' && _dbg_dict.find(a[i + 1]) != _dbg_dict.end() ? _dbg_dict[a[++i]] : string(1, a[i]));
}
#define dbg1(a) _dbg_print(#a, a);
#define dbg2(a, b) dbg1(a) dbg1(b)
#define dbg3(a, b, c) dbg1(a) dbg2(b, c)
#define dbg4(a, b, c, d) dbg1(a) dbg3(b, c, d)
#define dbg5(a, b, c, d, e) dbg1(a) dbg4(b, c, d, e)
#define dbg6(a, b, c, d, e, f) dbg1(a) dbg5(b, c, d, e, f)
#define dbg7(a, b, c, d, e, f, g) dbg1(a) dbg6(b, c, d, e, f, g)
#define dbg8(a, b, c, d, e, f, g, h) dbg1(a) dbg7(b, c, d, e, f, g, h)
#define dbg9(a, b, c, d, e, f, g, h, i) dbg1(a) dbg8(b, c, d, e, f, g, h, i)
#define dbg10(a, b, c, d, e, f, g, h, i, j) dbg1(a) dbg9(b, c, d, e, f, g, h, i, j)
#define dbg11(a, b, c, d, e, f, g, h, i, j, k) dbg1(a) dbg10(b, c, d, e, f, g, h, i, j, k)
#define dbg12(a, b, c, d, e, f, g, h, i, j, k, l) dbg1(a) dbg11(b, c, d, e, f, g, h, i, j, k, l)
#define dbg13(a, b, c, d, e, f, g, h, i, j, k, l, m) dbg1(a) dbg12(b, c, d, e, f, g, h, i, j, k, l, m)
#define dbg14(a, b, c, d, e, f, g, h, i, j, k, l, m, n) dbg1(a) dbg13(b, c, d, e, f, g, h, i, j, k, l, m, n)
#define dbg15(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o) dbg1(a) dbg14(b, c, d, e, f, g, h, i, j, k, l, m, n, o)
#define dbg16(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p) dbg1(a) dbg15(b, c, d, e, f, g, h, i, j, k, l, m, n, o, p)
#define get_dbg(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, _14, _15, _16, NAME, ...) NAME
#define dbg(...) get_dbg(__VA_ARGS__, dbg16, dbg15, dbg14, dbg13, dbg12, dbg11, dbg10, dbg9, dbg8, \
dbg7, dbg6, dbg5, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__)
#else
#define dbg(...)
#endif
#pragma endregion debug
#pragma region y_combinator
#ifndef Y_COMBINATOR_HPP
#define Y_COMBINATOR_HPP
template<class Fun>
class y_combinator_result {
Fun fun_;
public:
template<class T>
explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
#endif
#pragma endregion y_combinator
namespace game {
int N, K;
vector<int> A, B;
vector<vector<int>> G, H;
void init_slow(int _N, int _K) {
N = _N;
K = _K;
A.assign(N, INT_MAX);
iota(A.begin(), A.begin() + K, 0);
B.assign(N, INT_MIN);
iota(B.begin(), B.begin() + K, 0);
G.resize(N);
H.resize(N);
}
bool add_teleporter_slow(int s, int t) {
if (s < K && t < K)
return t <= s;
G[s].push_back(t);
H[t].push_back(s);
auto dfsa = y_combinator([&](auto dfsa, int u, int k) -> bool {
if (A[u] <= k)
return false;
A[u] = k;
if (A[u] <= B[u])
return true;
for (int v : H[u])
if (dfsa(v, k))
return true;
return false;
});
auto dfsb = y_combinator([&](auto dfsb, int u, int k) -> bool {
if (k <= B[u])
return false;
B[u] = k;
if (A[u] <= B[u])
return true;
for (int v : G[u])
if (dfsb(v, k))
return true;
return false;
});
return dfsa(s, A[t]) || dfsb(t, B[s]);
}
const int S = 100;
vector<int> C, D;
void init_fast(int _N, int _K) {
N = _N;
K = _K;
A.assign(N, INT_MAX);
B.assign(N, INT_MIN);
C.assign(N, INT_MAX);
D.assign(N, INT_MIN);
for (int i = 0; i < K; i++) {
A[i] = i;
B[i] = i;
C[i] = i / S;
D[i] = i / S;
}
G.resize(N);
H.resize(N);
dbg("_4\n", A, B, C, D);
}
bool add_teleporter_fast(int s, int t) {
if (s < K && t < K)
return t <= s;
G[s].push_back(t);
H[t].push_back(s);
int p = -1;
auto dfsc = y_combinator([&](auto dfsc, int u, int k) -> bool {
if (C[u] <= k)
return false;
C[u] = k;
if (C[u] < D[u] || A[u] <= B[u])
return true;
else if (C[u] == D[u])
p = u;
for (int v : H[u])
if (dfsc(v, k))
return true;
return false;
});
auto dfsd = y_combinator([&](auto dfsd, int u, int k) -> bool {
if (k <= D[u])
return false;
D[u] = k;
if (C[u] < D[u] || A[u] <= B[u])
return true;
else if (C[u] == D[u])
p = u;
for (int v : G[u])
if (dfsd(v, k))
return true;
return false;
});
if (dfsc(s, C[t]) || dfsd(t, D[s]))
return true;
dbg("_4\n", s, t, A, B, C, D);
if (p == -1)
return false;
int b = C[p];
auto dfsa = y_combinator([&](auto dfsa, int u, int k) -> bool {
if (A[u] <= k)
return false;
A[u] = k;
if (A[u] <= B[u])
return true;
for (int v : H[u])
if (C[v] == D[v] && C[v] == b && dfsa(v, k))
return true;
return false;
});
auto dfsb = y_combinator([&](auto dfsb, int u, int k) -> bool {
if (k <= B[u])
return false;
B[u] = k;
if (A[u] <= B[u])
return true;
for (int v : G[u])
if (C[v] == D[v] && C[v] == b && dfsb(v, k))
return true;
return false;
});
for (int i = b * S; i < min((b + 1) * S, K); i++) {
for (int v : H[i])
if (C[v] == D[v] && C[v] == b && dfsa(v, A[i]))
return true;
for (int v : G[i])
if (C[v] == D[v] && C[v] == b && dfsb(v, B[i]));
return true;
}
dbg(A, B, C, D);
return false;
}
}
void init(int N, int K) { game::init_fast(N, K); }
int add_teleporter(int u, int v) { return game::add_teleporter_fast(u, v); }
/*
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
int N = read_int();
int M = read_int();
int K = read_int();
std::vector<int> u(M), v(M);
for (int i = 0; i < M; ++i) {
u[i] = read_int();
v[i] = read_int();
}
init(N, K);
int i;
for (i = 0; i < M; ++i) {
int answer = add_teleporter(u[i], v[i]);
if (answer != 0 && answer != 1) {
i = -1;
break;
} else if (answer == 1) {
break;
}
}
printf("%d\n", i);
return 0;
}
*/
#undef NDEBUG
详细
Subtask #1:
score: 2
Accepted
Test #1:
score: 2
Accepted
time: 0ms
memory: 3888kb
input:
1 1 1 893123 893123 -1
output:
0
result:
ok interaction finished.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
9 9 29 893122 893124 893121 893127 893120 893124 893123 893121 893122 893131 893125 893131 893121 893126 893123 893126 893126 893131 893123 893131 893123 893125 893123 893124 893127 893125 893120 893126 893123 893120 893121 893131 893123 893127 893122 893126 893122 893127 893127 893131 893122 893125...
output:
28
result:
ok interaction finished.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
100 100 80 893180 893071 893134 893063 893150 893091 893127 893178 893142 893177 893153 893156 893127 893137 893174 893065 893127 893070 893126 893061 893171 893089 893173 893072 893153 893058 893156 893074 893151 893068 893136 893060 893120 893083 893073 893091 893148 893163 893073 893088 893156 89...
output:
80 80 80 59
result:
ok interaction finished.
Test #4:
score: 0
Accepted
time: 1ms
memory: 3956kb
input:
45 45 80 893143 893167 893122 893132 893123 893140 893120 893139 893158 893167 893154 893163 893133 893137 893133 893142 893135 893137 893121 893135 893137 893149 893141 893152 893122 893167 893128 893145 893140 893167 893122 893127 893134 893142 893122 893129 893141 893156 893146 893149 893123 8931...
output:
80 49
result:
ok interaction finished.
Test #5:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
100 100 80 893169 893058 893132 893065 893143 893068 893153 893167 893152 893182 893138 893162 893129 893163 893146 893164 893134 893180 893142 893167 893144 893059 893132 893064 893135 893091 893164 893068 893123 893179 893126 893060 893136 893140 893179 893081 893139 893181 893120 893057 893172 89...
output:
80 80 80 42
result:
ok interaction finished.
Test #6:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
100 100 80 893135 893081 893170 893076 893148 893075 893134 893159 893159 893073 893170 893088 893131 893138 893121 893166 893171 893168 893127 893137 893147 893145 893062 893076 893160 893059 893063 893088 893137 893073 893123 893182 893152 893170 893141 893172 893137 893087 893167 893085 893147 89...
output:
80 80 80 37
result:
ok interaction finished.
Test #7:
score: 0
Accepted
time: 1ms
memory: 3896kb
input:
100 100 80 893062 893075 893139 893156 893137 893083 893071 893075 893072 893080 893141 893060 893126 893179 893064 893081 893167 893077 893139 893165 893056 893085 893169 893182 893062 893087 893141 893078 893062 893078 893129 893176 893065 893077 893141 893181 893152 893158 893151 893078 893157 89...
output:
80 80 80 59
result:
ok interaction finished.
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #8:
score: 0
Wrong Answer
time: 0ms
memory: 3808kb
input:
100 10 80 893135 893150 893174 893168 893159 893149 893162 893082 893158 893129 893072 893150 893088 893079 893155 893154 893086 893126 893078 893153 893177 893138 893057 893066 893151 893089 893076 893162 893165 893164 893085 893170 893084 893128 893074 893083 893138 893148 893147 893167 893071 893...
output:
80 26
result:
wrong answer Wrong Answer [1]
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%