제출 #1207818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1207818		quicksloth	Permutation Game (APIO25_permgame)	C++20	12 / 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++)

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);
}

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