QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#378290#8566. Can We Still Qualify For Semifinals?ucup-team2112#WA 1ms3832kbC++205.4kb2024-04-06 10:52:172024-04-06 10:52:17

Judging History

你现在查看的是最新测评结果

  • [2024-04-06 10:52:17]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3832kb
  • [2024-04-06 10:52:17]
  • 提交

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]