Submission #1205430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205430		Ghulam_Junaid	Permutation Game (APIO25_permgame)	C++20	22 / 100	11 ms	328 KiB

permgame

#include <bits/stdc++.h>
#include "permgame.h"
using namespace std;

int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
    int cnt = 0;
    for (int i = 0; i < n; i ++)
        cnt += (p[i] == i);

    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]);
    }
    for (int i = 0; i < m; i ++)
        if (g[i].size() > 2)
            return cnt;

    bool vis[n] = {};
    vector<int> order;
    int ver = 0;
    for (int i = 0; i < m; i ++)
        if (g[ver].size() > g[i].size())
            ver = i;
    while (1){
        order.push_back(ver);
        vis[ver] = 1;

        int nxt = g[ver][0];
        if (vis[nxt] and g[ver].size() > 1) nxt = g[ver][1];
        if (vis[nxt]) break;
        ver = nxt;
    }

    int ind[n];
    while (1){
        vector<vector<int>> vec;
        vector<int> cyc;
        for (int i = 0; i < n; i ++)
            ind[p[i]] = i;

        memset(vis, 0, sizeof vis);
        for (int i = 0; i < n; i ++){
            if (vis[i]) continue;
            cyc.clear();

            int v = i;
            while (1){
                cyc.push_back(v);
                vis[v] = 1;
                v = p[v];
                if (vis[v]) break;
            }
            vec.push_back(cyc);
        }

        int cur_ans = 0;
        vector<int> tmp;
        for (vector<int> cyc : vec){
            if (cyc.size() == 1){
                cur_ans++;
                continue;
            }
            for (int x : cyc)
                tmp.push_back(x);
        }

        if (tmp.size() < m) return cur_ans;
        vector<int> t;
        for (int i = 0; i < m; i ++)
            t.push_back(tmp[order[i]]);
        
        int e = Bob(t);
        swap(p[t[u[e]]], p[t[v[e]]]);
    }

    while (1){
        vector<vector<int>> vec;
        vector<int> cyc;
        for (int i = 0; i < n; i ++)
            ind[p[i]] = i;

        memset(vis, 0, sizeof vis);
        for (int i = 0; i < n; i ++){
            if (vis[i]) continue;
            cyc.clear();

            int v = i;
            while (1){
                cyc.push_back(v);
                vis[v] = 1;
                v = p[v];
                if (vis[v]) break;
            }
            vec.push_back(cyc);
        }

        bool all_bad = 1;
        int cur_ans = 0;
        for (vector<int> cyc : vec){
            cur_ans += (cyc.size() == 1);
            if (cyc.size() > 1 and (cyc.size()) % (m - 1) == 1)
                all_bad = 0;
        }

        if (all_bad){
            int ind1 = -1, ind2 = -1;
            for (int i = 0; i < vec.size(); i ++){
                if (vec[i].size() % (m - 1) == 2 and ind1 == -1)
                    ind1 = i;
                else if (vec[i].size() % (m - 1) == 2)
                    ind2 = i;
            }
            if (ind2 == -1) return cur_ans;
            vector<int> tmp;
            tmp.push_back(vec[ind1][0]);
            tmp.push_back(vec[ind1][1]);
            tmp.push_back(vec[ind2][0]);
            tmp.push_back(vec[ind2][1]);

            vector<int> t;
            for (int i = 0; i < m; i ++)
                t.push_back(tmp[order[i]]);

            int e = Bob(t);
            swap(p[t[u[e]]], p[t[v[e]]]);
            continue;
        }

        for (vector<int> cyc : vec){
            if (cyc.size() < m) continue;
            if (cyc.size() % (m - 1) != 1) continue;
            vector<int> t;
            for (int i = 0; i < m; i ++)
                t.push_back(cyc[order[i]]);
            int e = Bob(t);
            swap(p[t[u[e]]], p[t[v[e]]]);
            break;
        }
    }
}

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