제출 #1303995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303995		Namnamseo	Permutation Game (APIO25_permgame)	C++20	46 / 100	10 ms	424 KiB

permgame

#include "permgame.h"
#include <bitset>
#include <vector>
#include <utility>
using namespace std;
#define sz(v) ((int)((v).size()))

#define _PERMGAME_SIGNATURE_ int m, int e, vector<int> u, vector<int> v, int n, vector<int> p
#define _PERMGAME_REF_SIGNATURE_ int m, int e, vector<int> &u, vector<int> &v, int n, vector<int> &p
#define params m, e, u, v, n, p
#define pb push_back

void _bob(vector<int> &mx, _PERMGAME_REF_SIGNATURE_) {
    int j = Bob(mx);
    int a = u[j], b = v[j];
    swap(p[mx[a]], p[mx[b]]);
}

int _count_score(_PERMGAME_REF_SIGNATURE_) {
    int ans = 0;
    for (int i=0; i<n; ++i) if (p[i] == i) ++ans;
    return ans;
}

int subtask1(_PERMGAME_REF_SIGNATURE_) {
    vector<int> mx(m);

while (true) {
    int broken;
    for (broken=0; broken<n; ++broken) if (p[broken] != broken) break;
    if (broken == n) break;

    mx[0] = broken; mx[1] = p[broken]; _bob(mx, params);
}

    return n;
}

int subtask2(_PERMGAME_REF_SIGNATURE_) { return _count_score(params); }

vector<vector<int>> _get_nonI_cycs(_PERMGAME_REF_SIGNATURE_) {
    static bitset<401> chk; chk.reset();
    vector<vector<int>> cycs;
    for (int ci=0; ci<n; ++ci) if (!chk[ci]) {
        if (p[ci] == ci) continue; // nonI part
        cycs.emplace_back();
        for (int x=ci;;) {
            cycs.back().pb(x); chk.set(x);
            x = p[x];
            if (chk[x]) break;
        }
    }
    return cycs;
}

int subtask3(_PERMGAME_REF_SIGNATURE_) {
    vector<int> deg(m);
    vector<int> es(m);
    vector<int> ends;
    for (int i=0; i<e; ++i) { ++deg[u[i]]; ++deg[v[i]]; es[u[i]] += v[i]; es[v[i]] += u[i]; }
    for (int i=0; i<m; ++i) {
        if (deg[i] > 2) return _count_score(params);
        else if (deg[i] == 1) ends.pb(i);
    }
    vector<int> line;
    for (int i=ends[0];;) {
        line.pb(i);
        if (i == ends[1]) break;
        int j = es[i];
        es[j] -= i; i = j;
    }

    vector<int> mx(m);
    while (true) {
        auto cycs = _get_nonI_cycs(params);

        int sz_sum = 0;
        for (auto &c: cycs) sz_sum += sz(c);
        if (sz_sum < sz(line)) break;
        { int mc = 0; for (auto &c: cycs) for (int x: c) {
            mx[line[mc++]] = x;
            if (mc == sz(line)) goto hehe;
        } }
        hehe:

        _bob(mx, params);
    }
    return _count_score(params);
}

vector<int> mcycle;
void _find_mgraph_cycle(_PERMGAME_REF_SIGNATURE_) {
    vector<int> deg(m), es(m);
    for (int i=0; i<e; ++i) {
        ++deg[u[i]], ++deg[v[i]];
        es[u[i]] += v[i];
        es[v[i]] += u[i];
    }
    for (int i=0; i<m; ++i) if (deg[i] != 2) return;

    mcycle.clear();
    es[u[0]] -= v[0];
    for (int x=u[0];;) {
        mcycle.pb(x);
        if (sz(mcycle) == m) break;
        int y=es[x]; es[y]-=x; x = y;
    }
}

int subtask4(_PERMGAME_REF_SIGNATURE_) {
    int expected_answer = 0;
    { 
        for (auto &c: _get_nonI_cycs(params)) {
            if (sz(c) >= 3 && sz(c)%2 == 1) {
                ++expected_answer;
            }
        }
        expected_answer += _count_score(params);
    }

    vector<int> mx(m);
    while (true) {
        auto cycs = _get_nonI_cycs(params);
        bool interesting = false;
        for (auto &c: cycs) if (sz(c) >= 3) {
            for (int i=0; i<m; ++i) {
                mx[mcycle[i]] = c[i];
            }
            _bob(mx, params);
            interesting = true;
            break;
        }
        if (!interesting) break;
    }

    return expected_answer;
}

int subtask5(_PERMGAME_REF_SIGNATURE_) {
    int expected_answer = _count_score(params);
    {
        int cnt2 = 0, cnt3 = 0;
        for (auto &c: _get_nonI_cycs(params)) {
            switch (sz(c)%3) {
                case 1: {
                    expected_answer++;
                    int q = (sz(c)-1)/3;
                    cnt2 += (q-1); expected_answer += (q-1); ++cnt3;
                } break;

                case 2: {
                    ++cnt2; cnt3 += (sz(c) - 2) / 3;
                } break;

                case 0: {
                    int q = sz(c)/3;
                    cnt2 += (q-1); expected_answer += (q-1); ++cnt3;
                } break;
            }
        }

        // if we jumble up all 3s...
        if (cnt3) { cnt2 += cnt3-1; expected_answer += cnt3-1; }
        // now make max use of 2s...
        if (cnt2 >= 4) { expected_answer += cnt2/2 - 1; }
    }

    vector<int> mx(m);
    vector<int> head2, head3;
    while (_count_score(params) < expected_answer) {
        auto cycs = _get_nonI_cycs(params);
        bool interesting = false;
        head2.clear(); head3.clear();

        for (auto &c: cycs) {
            if (sz(c) >= 4) {
                for (int i=0; i<m; ++i) {
                    mx[mcycle[i]] = c[i];
                }
                _bob(mx, params);
                interesting = true;
            } else if (sz(c) == 2) head2.pb(c[0]);
            else if (sz(c) == 3) head3.pb(c[0]);
        }
        if (interesting) continue;

        if (sz(head3) >= 2) {
            if (sz(head3) >= 4) {
                for (int i=0; i<m; ++i) mx[mcycle[i]] = head3[i];
                _bob(mx, params);
                continue;
            }
            if (sz(head3) == 3) {
                mx[mcycle[0]] = head3[0];
                mx[mcycle[1]] = p[head3[0]];
                mx[mcycle[2]] = head3[1];
                mx[mcycle[3]] = head3[2];
            } else {
                mx[mcycle[0]] = head3[0];
                mx[mcycle[1]] = p[head3[0]];
                mx[mcycle[2]] = p[p[head3[0]]];
                mx[mcycle[3]] = head3[1];
            }
            _bob(mx, params); continue;
        }

        if (sz(head2) >= 2) {
            mx[mcycle[0]] = head2[0];
            mx[mcycle[1]] = p[head2[0]];
            mx[mcycle[2]] = head2[1];
            mx[mcycle[3]] = p[head2[1]];
            _bob(mx, params); continue;
        }

        break;
    }

    return expected_answer;
}

int Alice(_PERMGAME_SIGNATURE_) {
    if (m == 2) return subtask1(params);
    if (e > m) return subtask2(params);
    if (e == m-1) return subtask3(params);
    // from now on, e == m.

    _find_mgraph_cycle(params);
    if (mcycle.empty()) return _count_score(params);

    if (m == 3) return subtask4(params);
    if (m == 4) return subtask5(params);

    return 42;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 24 / 24
• Subtask 5: 0 / 24
• Subtask 6: 0 / 30