Submission #1208645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208645		Ludissey	Permutation Game (APIO25_permgame)	C++20	30 / 100	2 ms	328 KiB

permgame

#include "permgame.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


using namespace std;


int Alice(int m, int e, std::vector<int> u, std::vector<int> v, int n, std::vector<int> p) {
    bool b=true;
    int c=0;
    vector<int> vt(n,0);
    vector<int> ed(m);
    for (int i = 0; i < e; i++) { ed[u[i]]++; ed[v[i]]++; }
    for (int i = 0; i < m; i++) if(ed[i]!=2) b=false;
    
    for (int i = 0; i < n; i++)
    {
        int x=i;
        if(vt[x]) continue;
        vector<int> q;
        while(!vt[x]){
            vt[x]=true;
            q.push_back(x);
            x=p[x];
        }
        if(sz(q)==1) c++;
        if(sz(q)>=m&&sz(q)%(m-1)==1&&b){
            c++;
        }
    }
    if(!b) return c;
    b=true;
    while(b){
        b=false;
        for (int i = 0; i < n; i++)
        {
            int x=i;
            vector<int> q;
            vector<int> visited(n,0);
            while(!visited[x]&&sz(q)<m){
                visited[x]=true;
                q.push_back(x);
                x=p[x];
            }
            if(sz(q)==m){
                int j=Bob(q);
                swap(p[q[u[j]]],p[q[v[j]]]);
                b=true;
                break;
            }
        }
    }
    return c;
}

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