Submission #1207558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207558		baluteshih	Permutation Game (APIO25_permgame)	C++20	46 / 100	10 ms	328 KiB

permgame

#include "permgame.h"
#ifndef __BALU_DEFAULT_CODE__
#define __BALU_DEFAULT_CODE__
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()
template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B> &a) {
    os << "(" << a.first << ", " << a.second << ")";
    return os;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T> &a) {
    os << "[ ";
    for (int i = 0; i < int(a.size()); ++i) {
        os << a[i];
        if (i + 1 < int(a.size()))
            os << ", ";
    }
    os << " ]";
    return os;
}
#ifdef bbq
#include <experimental/iterator>
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

#endif // __BALU_DEFAULT_CODE__

int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
    
    auto cal = [&]() {
        int ans = 0;
        for (int i = 0; i < n; ++i)
            ans += p[i] == i;
        return ans;
    };

    if (e > m) return cal();
    vector<int> t(m);

    auto run = [&]() {
        debug(t);
        int j = Bob(t);
        swap(p[t[u[j]]], p[t[v[j]]]);
    };

    vector<vector<int>> G(m);
    for (int i = 0; i < e; ++i) {
        G[u[i]].pb(v[i]);
        G[v[i]].pb(u[i]);
    }

    int s = 0;
    for (int i = 0; i < m; ++i) {
        if (SZ(G[i]) > 2) return cal();
        if (SZ(G[i]) == 1)
            s = i;
    }

    vector<int> ord;

    {
        vector<int> vis(m);
        auto dfs = [&](auto _dfs, int u) -> void {
            ord.pb(u), vis[u] = 1;
            for (int i : G[u])
                if (!vis[i])
                    _dfs(_dfs, i);
        };
        dfs(dfs, s);
    }

    auto handle4 = [&]() {
        bool succ = false;
        while (true) {
            vector<int> vis(n);
            vector<int> buk;
            for (int i = 0; i < n; ++i) {
                if (p[i] == i || vis[i]) continue;
                vector<int> internal;
                for (int j = i; !vis[j]; j = p[j])
                    internal.pb(j), vis[j] = 1;
                if (SZ(internal) >= 4) {
                    buk = internal;
                    break;
                }
            } 
            if (buk.empty()) break;
            succ = true;
            for (int i = 0; i < m; ++i)
                t[ord[i]] = buk[i];
            run();
        }
        return succ;
    };

    auto handle6 = [&]() {
        vector<int> vis(n);
        vector<int> buk;
        for (int i = 0; i < n; ++i) {
            if (p[i] == i) continue;
            vector<int> internal;
            for (int j = i; !vis[j]; j = p[j])
                internal.pb(j), vis[j] = 1;
            if (SZ(internal) == 6) {
                buk = internal;
                break;
            }
        } 
        if (buk.empty()) return false;
        t[ord[0]] = buk[0];
        t[ord[1]] = buk[1];
        t[ord[2]] = buk[2];
        t[ord[3]] = buk[4];
        run();
        handle4();
        return true;
    };

    auto handle22 = [&]() {
        vector<int> vis(n);
        vector<int> buk;
        for (int i = 0; i < n; ++i) {
            if (p[i] == i || vis[i]) continue;
            vector<int> internal;
            for (int j = i; !vis[j]; j = p[j])
                internal.pb(j), vis[j] = 1;
            if (SZ(internal) == 2) {
                buk.insert(buk.end(), ALL(internal));
                if (SZ(buk) == 4) break;
            }
        } 
        if (SZ(buk) < 4) return false;
        t[ord[0]] = buk[0];
        t[ord[1]] = buk[1];
        t[ord[2]] = buk[2];
        t[ord[3]] = buk[3];
        run();
        handle4();
        return true;
    };

    auto handle33 = [&]() {
        vector<int> vis(n);
        vector<int> buk;
        for (int i = 0; i < n; ++i) {
            if (p[i] == i || vis[i]) continue;
            vector<int> internal;
            for (int j = i; !vis[j]; j = p[j])
                internal.pb(j), vis[j] = 1;
            if (SZ(internal) == 3) {
                buk.insert(buk.end(), ALL(internal));
                if (SZ(buk) == 6) break;
            }
        } 
        if (SZ(buk) < 6) return false;
        t[ord[0]] = buk[0];
        t[ord[1]] = buk[1];
        t[ord[2]] = buk[2];
        t[ord[3]] = buk[3];
        run();
        handle4();
        return true;
    };

    int score = -1;
    while (true) {
        vector<int> vis(n);
        vector<int> buk;
        int odd = 0, two = 0, three = 0;
        for (int i = 0; i < n; ++i) {
            if (p[i] == i || vis[i]) continue;
            vector<int> internal;
            for (int j = i; !vis[j]; j = p[j])
                internal.pb(j), vis[j] = 1;
            if (m - 1 == e) {
                buk.insert(buk.end(), ALL(internal));
            }
            else {
                if (m == e && m == 4) {
                    if (SZ(internal) > 3) {
                        buk.insert(buk.end(), ALL(internal));
                        three += SZ(internal) / 3;
                        if (SZ(internal) % 3 == 2) ++two;
                        if (SZ(internal) % 3 == 1) ++odd;

                    }
                    if (SZ(internal) == 3) ++three;
                    if (SZ(internal) == 2) ++two;
                }
                else {
                    if (SZ(internal) > 2) 
                        buk.insert(buk.end(), ALL(internal));
                    if (SZ(internal) & 1)
                        ++odd;
                }
            }
        }
        if (score == -1) { 
            if (m == 3) score = cal() + odd;
            else {
                score = cal() + odd;
                debug(score, two, three);
                while (two + three >= 3 || (two + three == 2 && (two == 0 || three == 0))) {
                    score += two / 2, three += two / 2, two %= 2;
                    score += three / 2, two += three / 2, three = three % 2 + three / 2;
                }
            }
        }
        if (SZ(buk) < m) {
            break;
        }
        for (int i = 0; i < m; ++i)
            t[ord[i]] = buk[i];
        run();
    }

    if (m == e && m == 4) {
        while (handle22() || handle33() || handle6() || handle4());     
    }

    if (m - 1 == e) return cal();
    return score;
}

• 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