Submission #1205900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205900		bronze_coder	Permutation Game (APIO25_permgame)	C++20	46 / 100	10 ms	328 KiB

permgame

#include "permgame.h"
#include <bits/stdc++.h>
using namespace std;

int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p){
    vector<int> degree(n,0);
    for(int i:u){
        degree[i]++;
    }
    for(int i:v){
        degree[i]++;
    }
    int ans = 0;
    for(int i=0;i<n;i++){
        if(p[i]==i){
            ans++;
        }
    }
    for(int i:degree){
        if(i>2){
            return ans;
        }
    }
    if(ans>n-m&&(m!=2||ans==n)){
        return ans;
    }

    vector<vector<int>> adj(m);
    for(int i=0;i<e;i++){
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }

    vector<int> order;

    for(int i=0;i<m;i++){
        if(adj[i].size()==1||e==m){
            order.push_back(i);
            i = adj[i][0];
            while(adj[i].size()==2&&i!=order[0]){
                order.push_back(i);
                if(adj[i][0]==order[order.size()-2]){
                    i = adj[i][1];
                }
                else{
                    i = adj[i][0];
                }
            }
            order.push_back(i);
            break;
        }
    }


    if(e==m-1){
        while(ans<n-m+2-min(m-2,1)){
            vector<int> visited(n,0);
            vector<int> query(m);
            int count = 0;
            for(int i=0;i<n;i++){
                if(p[i]!=i&&visited[i]==0&&count<m){
                    int j = i;
                    while(visited[j]==0&&count<m){
                        query[order[count]] = j;
                        visited[j] = 1;
                        j = p[j];
                        count++;
                    }
                    visited[i] = 1;
                }
            }
            int t = Bob(query);
            swap(p[query[u[t]]],p[query[v[t]]]);
            ans = 0;
            for(int i=0;i<n;i++){
                if(p[i]==i){
                    ans++;
                }
            }
        }
        return n-m+2-min(m-2,1);
    }

    if(e==m){
        int best = 0;
        if(m%2==1){
            vector<int> visited(n,0);
            vector<int> s(n,0);
            for(int i=0;i<n;i++){
                if(visited[i]==0&&p[i]!=i){
                    int j = i;
                    while(visited[j]==0){
                        if(j!=i){
                            s[j] = i;
                        }
                        visited[j] = 1;
                        j = p[j];
                        s[i]--;
                    }
                }
            }
            int total = 0;
            vector<int> c;
            int count = 0;
            for(int i=0;i<n;i++){
                if(s[i]<0&&(-s[i])%2==0){
                    total -= s[i];
                }
                else if(s[i]<0&&(-s[i])%2==1){
                    c.push_back(-s[i]);
                    count++;
                }
            }
            sort(c.begin(),c.end());
            best = ans+count;
            if(total<m){
                for(int i=c.size()-1;i>=0;i--){
                    total += c[i];
                    if(total<m){
                        best--;
                    }
                    else{
                        break;
                    }
                }
            }
            while(ans<best){
                vector<int> visited(n,0);
                vector<int> s(n,0);
                for(int i=0;i<n;i++){
                    if(visited[i]==0&&p[i]!=i){
                        int j = i;
                        while(visited[j]==0){
                            if(j!=i){
                                s[j] = i;
                            }
                            visited[j] = 1;
                            j = p[j];
                            s[i]--;
                        }
                    }
                }
                vector<pair<int,int>> c;
                vector<pair<int,int>> d;
                for(int i=0;i<n;i++){
                    if(s[i]<0&&(-s[i])%2==1){
                        c.push_back({-s[i],i});
                    }
                    else if(s[i]<0){
                        d.push_back({-s[i],i});
                    }
                }
                sort(c.begin(),c.end());
                sort(d.begin(),d.end());
                vector<int> query(m);
                if(c.size()>0&&c[c.size()-1].first>=m){
                    int i = c[c.size()-1].second;
                    for(int count=0;count<m;count++){
                        query[order[count]] = i;
                        i = p[i];
                        if(count==m-2&&c[c.size()-1].first>m){
                            i = p[i];
                        }
                    }
                }
                else if(d[d.size()-1].first>=m-1){
                    int count = 0;
                    query[order[0]] = c[c.size()-1].second;
                    count++;
                    int i = d[d.size()-1].second;
                    while(count<m){
                        query[order[count]] = i;
                        i = p[i];
                        count++;
                    }
                }
                else{
                    int count = 0;
                    vector<int> visited(n,0);
                    for(int i=0;i<d.size();i++){
                        int j = d[i].second;
                        while(visited[j]==0&&count<m){
                            visited[j] = 1;
                            query[order[count]] = j;
                            count++;
                            j = p[j];
                        }
                    }
                    for(int i=c.size()-1;i>=0;i--){
                        int j = c[i].second;
                        while(visited[j]==0&&count<m){
                            visited[j] = 1;
                            query[order[count]] = j;
                            count++;
                            j = p[j];
                        }
                    }
                }
                int t = Bob(query);
                swap(p[query[u[t]]],p[query[v[t]]]);
                
                ans = 0;
                for(int i=0;i<n;i++){
                    if(p[i]==i){
                        ans++;
                    }
                }
            }
        }
        else{
            vector<int> visited(n,0);
            vector<int> s(n,0);
            for(int i=0;i<n;i++){
                if(visited[i]==0&&p[i]!=i){
                    int j = i;
                    while(visited[j]==0){
                        if(j!=i){
                            s[j] = i;
                        }
                        visited[j] = 1;
                        j = p[j];
                        s[i]--;
                    }
                }
            }
            int total = 0;
            for(int i:s){
                if(i<0){
                    total -= i;
                }
            }
            if(total==m){
                best = n-m+1;
                while(ans<best){
                    vector<int> visited(n,0);
                    vector<int> query(m);
                    int count = 0;
                    for(int i=0;i<n;i++){
                        if(visited[i]==0&&s[i]<0){
                            int j = i;
                            while(visited[j]==0){
                                visited[j] = 1;
                                query[order[count]] = j;
                                j = p[j];
                                count++;
                            }
                        }
                    }
                    int t = Bob(query);
                    swap(p[query[u[t]]],p[query[v[t]]]);
                    
                    ans = 0;
                    for(int i=0;i<n;i++){
                        if(p[i]==i){
                            ans++;
                        }
                    }
                }
            }
            else{
                best = n-m-1;
                while(ans<best){
                    vector<int> visited(n,0);
                    vector<int> s(n,0);
                    for(int i=0;i<n;i++){
                        if(visited[i]==0&&p[i]!=i){
                            int j = i;
                            while(visited[j]==0){
                                if(j!=i){
                                    s[j] = i;
                                }
                                visited[j] = 1;
                                j = p[j];
                                s[i]--;
                            }
                        }
                    }
                    vector<int> query(m);
                    int y = 0;
                    for(int i=0;i<n;i++){
                        if(s[i]==-m){
                            int j = i;
                            for(int z=0;z<m;z++){
                                query[order[z]] = j;
                                j = p[j];
                                y = 1;
                            }
                            break;
                        }
                    }
                    if(y==0){
                        for(int i=0;i<n;i++){
                            if(s[i]<=-m-2&&s[i]!=-m-3){
                                int j = i;
                                for(int z=0;z<m;z++){
                                    query[order[z]] = j;
                                    j = p[j];
                                    if(z==m-2){
                                        j = p[j];
                                    }
                                    y = 1;
                                }
                                break;
                            }
                        }
                    }
                    if(y==0){
                        for(int i=0;i<n;i++){
                            if(s[i]==-m-3){
                                vector<int> o;
                                int j = i;
                                o.push_back(j);
                                j = p[j];
                                while(j!=i){
                                    o.push_back(j);
                                    j = p[j];
                                }
                                for(int z=0;z<m;z++){
                                    if(z<m/2){
                                        query[order[z]] = p[2*z+z%2];
                                    }
                                    else if(m%4==0){
                                        query[order[z]] = p[m-1-2*(z-m/2)-(z-m/2+1)%2];
                                    }
                                    else{
                                        query[order[z]] = p[m-1-2*(z-m/2)-(z-m/2)%2];
                                    }
                                }
                                y = 1;
                                break;
                            }
                        }
                    }
                    if(y==0){
                        vector<pair<int,int>> c;
                        for(int i=0;i<n;i++){
                            c.push_back({-s[i],i});
                        }
                        sort(c.begin(),c.end());
                        int count = 0;
                        vector<int> visited(n,0);
                        for(int i=c.size()-1;i>=0;i--){
                            int j = c[i].second;
                            while(count<m&&visited[j]==0){
                                query[order[count]] = j;
                                j = p[j];
                                count++;
                            }
                        }
                    }
                    int t = Bob(query);
                    swap(p[query[u[t]]],p[query[v[t]]]);
                    
                    ans = 0;
                    for(int i=0;i<n;i++){
                        if(p[i]==i){
                            ans++;
                        }
                    }
                }
            }
        }
        return best;
    }
}

Compilation message (stderr)

permgame.cpp: In function 'int Alice(int, int, std::vector<int>, std::vector<int>, int, std::vector<int>)':
permgame.cpp:365:1: warning: control reaches end of non-void function [-Wreturn-type]
  365 | }
      | ^

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