Submission #1207828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207828		quicksloth	Permutation Game (APIO25_permgame)	C++20	36 / 100	1 ms	328 KiB

permgame

#include <vector>
using namespace std;
template<class C> using vc=vector<C>;
#define For(i,a,b) for(int i=(a);i<(b);i++)
const int mx=400;

int Bob(vc<int> t);

int Alice(int m, int e, vc<int> u, vc<int> v, int n, vc<int> p) {
    /*
    graph with m vertices e edges
    max fixed points in permutation of size n>=m
    3n steps: pick m indices, bob swaps a pair corresponding to an edge
    if some edge is not i-a[i] in any direction, cannot gain fixed points
    */
    if(m==2) {
        // n-1 swaps
        For(i,0,n) if(p[i]!=i)
            For(j,i+1,n) if(p[j]==i) p[j]=p[i], p[i]=i, Bob({i,j});
        return n;
    }
    else if(e>m) {
        // too many edges
        int ans=0;
        For(i,0,n) if(p[i]==i) ans++;
        return ans;
    }
    else if(e<m) {
        // not path: deg 3
        // path: ?
        ;
    }
    else if(m==3&&e==3) {
        /*
        C_3: answer = no. odd cycles
        proof: if pick two from different cycles, join
        else if all in even cycle, swap a pair with an even gap
        construction: shrink cycles
        */
        int ans=0;
        bool vis[mx]={};
        For(i,0,n) if(!vis[i]) {
            vc<int> V={i};
            while(p[V.back()]!=i) V.push_back(p[V.back()]);
            for(int t:V) vis[t]=1;
            if(V.size()&1) {
                ans++;
                while(V.size()>1) {
                    // operate on last 3
                    int res=Bob({V[V.size()-3],V[V.size()-2],V[V.size()-1]});
                    int x=u[res], y=v[res];
                    if(x==1||y==1) break; // got fixed point
                    V.pop_back(), V.pop_back();
                }
            }
        }
        return ans;
    }
    else {
        /*
        not cycle: deg 3
        cycle: ?
        */
    }
    throw(0);
}

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