QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#378290 | #8566. Can We Still Qualify For Semifinals? | ucup-team2112# | WA | 1ms | 3832kb | C++20 | 5.4kb | 2024-04-06 10:52:17 | 2024-04-06 10:52:17 |
Judging History
answer
#include <bits/stdc++.h>
template<class T>
struct Dinic {
const int n;
struct edge {
int to;
T cap;
edge(int to, T cap) : to(to), cap(cap) {}
};
std::vector<edge> e;
std::vector<std::vector<int> > adj;
std::vector<int> cur, h;
Dinic(int n) : n(n), adj(n) {}
bool bfs(int s, int t) {
h.assign(n, -1);
std::queue<int> que;
h[s] = 0;
que.push(s);
while (!que.empty()) {
const int u = que.front();
que.pop();
for (int i : adj[u]) {
auto [v, c] = e[i];
if (c > 0 && h[v] == -1) {
h[v] = h[u] + 1;
if (v == t) {
return true;
}
que.push(v);
}
}
}
return false;
}
T dfs(int u, int t, T f) {
if (u == t) {
return f;
}
auto r = f;
for (int &i = cur[u]; i < int(adj[u].size()); ++i) {
const int j = adj[u][i];
auto [v, c] = e[j];
if (c > 0 && h[v] == h[u] + 1) {
auto a = dfs(v, t, std::min(r, c));
e[j].cap -= a;
e[j ^ 1].cap += a;
r -= a;
if (r == 0) {
return f;
}
}
}
return f - r;
}
void addedge(int u, int v, T c) {
adj[u].push_back(e.size());
e.emplace_back(v, c);
adj[v].push_back(e.size());
e.emplace_back(u, 0);
}
T maxflow(int s, int t) {
T ans = 0;
while (bfs(s, t)) {
cur.assign(n, 0);
ans += dfs(s, t, std::numeric_limits<T>::max());
}
return ans;
}
};
void solve(){
int n;
std::string s;
std::cin >> n >> s;
std::vector<std::pair<int, int> > match;
{
std::vector<int> team(10);
std::iota(team.begin(), team.end(), 0);
for (int i = 0; i < 10; i += 1) {
for (int l = 0, r = 9; l < r; l += 1, r -= 1) {
match.emplace_back(team[l], team[r]);
// std::cerr << team[l] + 1 << " " << team[r] + 1 << "\n";
}
std::reverse(team.begin() + 1, team.end());
std::rotate(team.begin() + 1, team.begin() + 2, team.end());
std::reverse(team.begin() + 1, team.end());
// for (auto x : team) {
// std::cerr << x << " ";
// }
// std::cerr << "\n";;
}
}
std::reverse(match.begin(), match.end());
std::vector<int> win(10);
for (auto c : s) {
auto [a, b] = match.back();
match.pop_back();
if (c == '1') {
win[a] += 1;
}
else {
win[b] += 1;
}
}
{
decltype(match) a;
for (int i = 0; i < match.size(); i += 1) {
auto [x, y] = match[i];
if (x == 0 or y == 0) {
win[0] += 1;
}
else {
a.emplace_back(x, y);
}
}
match = a;
}
int v = win[0];
for (int i = 1; i < 10; i += 1) {
for (int j = i + 1; j < 10; j += 1) {
for (int k = j + 1; k < 10; k += 1) {
decltype(match) new_match;
for (auto [x, y] : match) {
if (x == i or x == j or x == k or y == i or y == j or y == k) {
continue;
}
new_match.emplace_back(x, y);
}
bool nice = true;
for (int x = 1; x < 10; x += 1) {
if (x == i or x == j or x == k) {
continue;
}
if (win[x] > v) {
nice = false;
break;
}
}
if (not nice) {
continue;
}
int nl = new_match.size();
int nr = 6;
Dinic<int> dinic(nl + nr + 2);
for (int i = 1; i <= nl; i += 1) {
dinic.addedge(0, i, 1);
}
std::vector<int> label(10);
for (int x = 1, c = 0; x < 10; x += 1) {
if (x == i or x == j or x == k) {
continue;
}
c += 1;
label[x] = c;
dinic.addedge(nl + c, nl + nr + 1, v - win[x]);
}
for (int i = 0; i < nl; i += 1) {
auto [x, y] = new_match[i];
x = label[x];
y = label[y];
dinic.addedge(i + 1, nl + x, 1);
dinic.addedge(i + 1, nl + y, 1);
}
int res = dinic.maxflow(0, nl + nr + 1);
if (res == nl) {
std::cout << "YES\n";
return;
}
}
}
}
std::cout << "NO\n";
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int T;
std::cin >> T;
while(T--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3628kb
input:
3 3 111 25 1000010101111111111010100 35 01111011110111101111011110111101111
output:
YES YES NO
result:
ok 3 token(s): yes count is 2, no count is 1
Test #2:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
10 16 0110000001010100 17 01111000110110101 15 001100010101111 16 0010101010011100 19 0000000100010110100 16 0011101010011100 18 011110010001100000 18 000110101001100011 20 01100010000100100100 15 001000111001101
output:
YES YES YES YES YES YES YES YES YES YES
result:
ok 10 token(s): yes count is 10, no count is 0
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3796kb
input:
10 37 0110000001010100011101001011100110001 39 000100111101101001100101101000000000100 35 00111000100111100101011010111100100 33 010000010001110010110001101110001 30 000100010100000010010110101010 31 0000101000011010101001010000000 44 00001000000111101011010110000101100011000100 42 01111011110001001...
output:
NO NO NO NO YES NO NO NO NO NO
result:
wrong answer expected NO, found YES [5th token]