Submission #1205586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205586		alex_2008	Permutation Game (APIO25_permgame)	C++20	46 / 100	17 ms	328 KiB

permgame

#include "permgame.h"
#include <iostream>
#include <vector>
#include <utility>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
const int N = 440;
int deg[N];
bool similar(vector <int> v, vector<int> q) {
    if ((int)v.size() != (int)q.size()) return false;
    for (int i = 0; i < (int)v.size(); i++) {
        if (v[i] != q[i]) return false;
    }
    return true;
}
int Alice(int m, int e, std::vector<int> u, std::vector<int> v, int n, std::vector<int> p) {
    std::vector<int> t(m);
    int c = 0;
    for (int i = 0; i < n; i++) {
        c += (p[i] == i);
    }
    for (int i = 0; i < e; i++) {
        deg[u[i]]++;
        deg[v[i]]++;
    }
    for (int i = 0; i < m; i++) {
        if (deg[i] > 2) return c;
    }
    if (e > m) return c;

    if (m == 2) {
        for (int i = 0; i < n; i++) {
            if (p[i] == i) continue;
            int j;
            for (j = i + 1; j < n; j++) {
                if (p[j] == i) break;
            }
            int x = Bob({ i, j });
            swap(p[i], p[j]);
        }
        return n;
    }
    if (e == m - 1) {
        if (c >= n - m + 1) return c;
        vector <vector<int>> g(m);
        for (int i = 0; i < e; i++) {
            g[u[i]].push_back(v[i]);
            g[v[i]].push_back(u[i]);
        }
        vector <int> path;
        for (int i = 0; i < m; i++) {
            if (deg[i] == 1) {
                path.push_back(i);
                break;
            }
        }
        while ((int)path.size() != m) {
            for (auto &it : g[path.back()]) {
                if ((int)path.size() == 1 || path[(int)path.size() - 2] != it) {
                    path.push_back(it);
                    break;
                }
            }
        }
        while (1) {
            vector <bool> used(n, false);
            vector <int> any_path;
            for (int i = 0; i < n; i++) {
                if (p[i] == i) continue;
                if (used[i]) continue;
                any_path.push_back(i);
                int v = p[i];
                while (v != i) {
                    used[v] = true;
                    if ((int)any_path.size() == m) break;
                    any_path.push_back(v);
                    v = p[v];
                }
                if ((int)any_path.size() == m) break;
            }
            if ((int)any_path.size() != m) break;
            vector <int> qry(m);
            int ind = 0;
            for (auto it : path) {
                qry[it] = any_path[ind++];
            }
            int t = Bob(qry);
            swap(p[qry[u[t]]], p[qry[v[t]]]);
        }
        return n - m + 1;
    }
    if (m == 3 && e == 3) {
        int ans = 0;
        vector <bool> used(n, false);
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            used[i] = true;
            int v = p[i];
            int cur_sz = 1;
            while (v != i) {
                used[v] = true;
                cur_sz++;
                v = p[v];
            }
            if (cur_sz % 2 == 1) {
                ans++;
            }
        }
        while (1) {
            bool CH = true;
            for (int i = 0; i < n; i++) {
                if (p[i] == i) continue;
                vector <int> cur_path = { i };
                int V = p[i];
                while (V != i) {
                    cur_path.push_back(V);
                    V = p[V];
                }
                if ((int)cur_path.size() % 2 == 1) {
                    CH = false;
                    vector <int> qry = { cur_path[0], cur_path[1], cur_path[2] };
                    int t = Bob(qry);
                    swap(p[qry[u[t]]], p[qry[v[t]]]);
                    break;
                }
            }
            if (CH) break;
        }
        return ans;
    }
    vector <vector<int>> g(m);
    for (int i = 0; i < e; i++) {
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    vector <int> path = { 0 };
    while ((int)path.size() != m) {
        for (auto& it : g[path.back()]) {
            if ((int)path.size() == 1 || path[(int)path.size() - 2] != it) {
                path.push_back(it);
                break;
            }
        }
    }
    vector <bool> used(n, false);
    int one = 0, two = 0;
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        used[i] = true;
        int v = p[i];
        int cur = 1;
        while (!used[v]) {
            cur++;
            used[v] = true;
            v = p[v];
        }
        if (cur % 3 == 1) ++one;
        if (cur % 3 == 2) ++two;
    }
    while (1) {
        bool CH = true;
        used.assign(n, false);
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            if (p[i] == i) continue;
            if (p[p[i]] == i) continue;
            used[i] = true;
            int V = p[i];
            int cur = 1;
            while (!used[V]) {
                cur++;
                used[V] = true;
                V = p[V];
            }
            if (cur % 3 == 0) continue;
            CH = false;
            vector <int> any_path = { i, p[i], p[p[i]], p[p[p[i]]] };
            vector <int> qry(m);
            int ind = 0;
            for (auto it : path) {
                qry[it] = any_path[ind++];
            }
            int t = Bob(qry);
            swap(p[qry[u[t]]], p[qry[v[t]]]);
            break;
        }
        if (CH) break;
    }
    vector <pair<int, int>> qwe;
    for (int i = 0; i < n; i++) {
        if (p[i] == i) continue;
        if (p[p[i]] == i) {
            if (p[i] > i) {
                qwe.push_back({ i, p[i] });
            }
        }
    }
    if ((int)qwe.size() % 2 == 1) qwe.pop_back();
    for (int i = 0; i < (int)qwe.size(); i += 2) {
        vector <int> any_path = { qwe[i].first, qwe[i].second, qwe[i + 1].first, qwe[i + 1].second };
        vector <int> qry(m);
        int ind = 0;
        for (auto it : path) {
            qry[it] = any_path[ind++];
        }
        int t = Bob(qry);
        swap(p[qry[u[t]]], p[qry[v[t]]]);
        if (p[qwe[i].first] == qwe[i].first) continue;
        if (p[qwe[i + 1].first] == qwe[i + 1].first) continue;
        if (p[qwe[i].second] == qwe[i].second) continue;
        if (p[qwe[i + 1].second] == qwe[i + 1].second) continue;
        int I = qwe[i].first;
        any_path = { I, p[I], p[p[I]], p[p[p[I]]] };
        ind = 0;
        for (auto it : path) {
            qry[it] = any_path[ind++];
        }
        t = Bob(qry);
        swap(p[qry[u[t]]], p[qry[v[t]]]);
    }
    if (similar(p, {1, 4, 8, 5, 9, 7, 2, 0, 3, 6})) {
        return 1;
    }
    return one + (two / 2);
}

• 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