Submission #1207818

#TimeUsernameProblemLanguageResultExecution timeMemory
1207818quickslothPermutation Game (APIO25_permgame)C++20
12 / 100
1 ms328 KiB
#include <vector>
using namespace std;
template<class C> using vc=vector<C>;
#define For(i,a,b) for(int i=(a);i<(b);i++)

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

    P_2: n-1 swaps
    e>m: too many edges
    deg 3: not functional
    tree, not path: deg 3
    path: ?
    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
    e=m, not cycle: deg 3
    C_m: ?
    */
    if(m==2) {
        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) {
        int ans=0;
        For(i,0,n) if(p[i]==i) ans++;
        return ans;
    }
    else if(e<m) {
        ;
    }
    else if(m==3&&e==3) {
        ;
    }
    throw(0);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...