Submission #1220722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220722		guagua0407	Permutation Game (APIO25_permgame)	C++20	70 / 100	11 ms	492 KiB

permgame

#include "permgame.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int Alice(int m, int e, std::vector<int> u, std::vector<int> v, int n, std::vector<int> p) {
    int cur=0;
    for(int i=0;i<n;i++){
        if(p[i]==i) cur++;
    }
    if(e>m) return cur;
    vector<vector<int>> adj(m);
    for(int i=0;i<e;i++){
        //cout<<u[i]<<' '<<v[i]<<'\n';
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    int st=0;
    for(int i=0;i<m;i++){
        if((int)adj[i].size()>2) return cur;
        if((int)adj[i].size()==1) st=i;
    }
    vector<int> ord;
    vector<bool> vis(m);
    while(!vis[st]){
        vis[st]=true;
        ord.push_back(st);
        int x=-1;
        for(auto v:adj[st]){
            if(!vis[v]){
                x=v;
                break;
            }
        }
        if(x==-1) break;
        st=x;
    }
    int best=0;
    {
        vector<bool> used(n);
        for(int i=0;i<n;i++){
            if(used[i]) continue;
            vector<int> tmp;
            int x=i;
            while(!used[x]){
                used[x]=true;
                tmp.push_back(x);
                x=p[x];
            }
            if((int)tmp.size()%2==1) best++;
        }
    }
    while(true){
        vector<vector<int>> cycle;
        vector<bool> used(n);
        for(int i=0;i<n;i++){
            if(used[i]) continue;
            vector<int> tmp;
            int x=i;
            while(!used[x]){
                used[x]=true;
                tmp.push_back(x);
                x=p[x];
            }
            if((int)tmp.size()>1) cycle.push_back(tmp);
        }
        vector<vector<int>> cnt(n+1);
        int mx=1;
        for(int i=0;i<(int)cycle.size();i++){
            cnt[(int)cycle[i].size()].push_back(i);
            mx=max(mx,(int)cycle[i].size());
        }
        vector<int> res(m,-1);
        if(e==m-1){
            for(int i=0;i<m;i++){
                if(cycle.empty()) break;
                if(cycle.back().empty()) cycle.pop_back();
                if(cycle.empty()) break;
                res[i]=cycle.back().back();
                cycle.back().pop_back();
            }
        }
        else if(m==3 and e==3){
            for(int i=3;i<=n;i+=2){
                if(!cnt[i].empty()){
                    int id=cnt[i][0];
                    for(int t=0;t<3;t++){
                        res[ord[t]]=cycle[id][t];
                    }
                }
            }
        }
        else{
            if((int)cnt[4].size()>=1){
                int id=cnt[4][0];
                for(int t=0;t<4;t++){
                    res[ord[t]]=cycle[id][t];
                }
            }
            else if(mx>5){
                int id=cnt[mx][0];
                vector<int> ord4={0,1,5,4};
                for(int t=0;t<4;t++){
                    res[ord[t]]=cycle[id][ord4[t]];
                }
            }
            else if((int)cnt[2].size()>1){
                int id1=cnt[2][0];
                int id2=cnt[2][1];
                for(int t=0;t<2;t++){
                    res[ord[t]]=cycle[id1][t];
                }
                for(int t=0;t<2;t++){
                    res[ord[t+2]]=cycle[id2][t];
                }
            }
            else if((int)cnt[3].size()>1){
                int id1=cnt[3][0];
                int id2=cnt[3][1];
                for(int t=0;t<2;t++){
                    res[ord[t]]=cycle[id1][t];
                }
                for(int t=0;t<2;t++){
                    res[ord[t+2]]=cycle[id2][t];
                }
            }
            else if(n>=5 and (int)cnt[5].size()>=1){
                int id1=cnt[5].back();
                cnt[5].pop_back();
                int id2=-1;
                for(int i=2;i<=5;i++){
                    if((int)cnt[i].size()>=1){
                        id2=cnt[i][0];
                        break;
                    }
                }
                if(id2!=-1){
                    for(int t=0;t<2;t++){
                        res[ord[t]]=cycle[id1][t];
                    }
                    for(int t=0;t<2;t++){
                        res[ord[t+2]]=cycle[id2][t];
                    }
                }
            }
        }
        if(res.back()==-1) break;
        int j=Bob(res);
        swap(p[res[u[j]]],p[res[v[j]]]);
        cur=0;
        for(int i=0;i<n;i++){
            if(p[i]==i) cur++;
        }
    }
    if(m==3 and e==3) return best;
    else return cur;
}
/*
3 3
0 1
1 2
2 0
10
8 2 7 6 1 5 0 9 3 4
*/

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