제출 #1311479

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311479		Lakshya108	Permutation Game (APIO25_permgame)	C++20	46 / 100	13 ms	512 KiB

permgame

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

#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second

int n, m;
vector<int> p, chain;
vector<pii> edges;
vector<vector<int>> vect, graph;

bool cmp(const vector<int>& a, const vector<int>& b){
    return a.size() > b.size();
}

int decomp(){
    vector<bool> vis(n, false);
    vect.clear();

    for(int i = 0; i < n; i++){
        if(!vis[i]){
            vector<int> cur;
            cur.pb(i);
            vis[i] = true;
            while(!vis[p[cur.back()]]){
                vis[p[cur.back()]] = true;
                cur.pb(p[cur.back()]);
            }
            vect.pb(cur);
        }
    }

    sort(vect.begin(), vect.end(), cmp);

    int res = 0;
    while(!vect.empty() && vect.back().size() == 1){
        res++;
        vect.pop_back();
    }
    return n - res;
}

void bob(const vector<int>& t){
    vector<int> res(m);
    for(int i = 0; i < m; i++)
        res[chain[i]] = t[i];

    int id = Bob(res);
    swap(p[res[edges[id].fi]], p[res[edges[id].se]]);
}

void odd(const vector<int>& t){
    vector<int> res;
    for(int i = 0; i < m; i += 2) res.pb(t[i]);
    for(int i = m - 2; i > 0; i -= 2) res.pb(t[i]);
    bob(res);
}

void even(const vector<int>& t){
    int c = 0;
    vector<int> res;
    res.pb(t[0]);

    for(int i = 0; i < m/2 - 1; i++){
        if(c % (2*(t.size() - m) - 2)) c++;
        else c += t.size() - m;
        res.pb(t[c]);
    }

    c++;
    res.pb(t[c]);
    c -= t.size() - m;
    res.pb(t[c]);

    for(int i = 0; i < m/2 - 2; i++){
        if(c % (2*(t.size() - m) - 2) == 1) c -= t.size() - m;
        else c--;
        res.pb(t[c]);
    }

    bob(res);
}

int Alice(int M, int E, vector<int> U, vector<int> V, int N, vector<int> P){
    n = N;
    m = M;
    p = P;

    graph.assign(n, {});
    edges.resize(E);

    if(m == 2){
        decomp();
        for(auto& c : vect)
            for(int i = 1; i < (int)c.size(); i++)
                Bob({c[0], c[i]});
        return n;
    }

    for(int i = 0; i < E; i++){
        graph[U[i]].pb(V[i]);
        graph[V[i]].pb(U[i]);
        edges[i] = {U[i], V[i]};
    }

    int ans = 0;
    for(int i = 0; i < n; i++)
        if(p[i] == i) ans++;

    bool bad = false;
    for(int i = 0; i < n; i++)
        if(graph[i].size() >= 3) bad = true;

    if(bad || ans >= n - m + 1)
        return ans;

    int start = 0;
    for(int i = 0; i < n; i++)
        if(graph[i].size() == 1)
            start = i;

    chain.clear();
    chain.pb(start);
    for(int i = 1; i < m; i++){
        int last = chain.back();
        if(chain.size() == 1 || graph[last][0] != chain[chain.size() - 2])
            chain.pb(graph[last][0]);
        else
            chain.pb(graph[last][1]);
    }

    if(E == m - 1 || (!(m % 2) && ans == n - m)){
        while(decomp() >= m){
            vector<int> t;
            for(auto& c : vect)
                for(int x : c)
                    t.pb(x);
            t.resize(m);
            bob(t);
        }
        return n - m + 1;
    }

    if(m % 2){
        int best = n - decomp();
        int oddc = 0, sum = 0, del = 0;

        for(auto& c : vect){
            if(c.size() % 2) oddc++;
            else sum += c.size();
        }

        for(auto& c : vect)
            if(c.size() % 2 && sum < m)
                sum += c.size(), del++;

        best += oddc - del + (del % 2);

        while(decomp() > n - best){
            bool done = false;
            for(auto& c : vect){
                if(c.size() % 2){
                    if(c.size() > m){
                        odd(c);
                        done = true;
                        break;
                    }
                    if(c.size() == m){
                        bob(c);
                        done = true;
                        break;
                    }
                }
            }
            if(!done){
                vector<int> t;
                for(auto& c : vect)
                    if(!(c.size() % 2))
                        for(int x : c) t.pb(x);

                while((int)t.size() >= m) t.pop_back();

                for(auto& c : vect)
                    if(c.size() % 2)
                        for(int x : c) t.pb(x);

                t.resize(m);
                bob(t);
            }
        }
        return best;
    }

    while(decomp() > m + 1){
        bool done = false;
        for(auto& c : vect){
            if(c.size() == m){
                bob(c);
                done = true;
                break;
            }
        }
        if(!done){
            for(auto& c : vect){
                if(c.size() >= m + 2){
                    even(c);
                    done = true;
                    break;
                }
            }
        }
        if(!done){
            int sum = 0;
            for(auto& c : vect)
                if(c.size() >= 3) sum += c.size();
            if(sum < m + 2) break;

            vector<int> t;
            for(auto& c : vect)
                for(int i = 0; i < min((int)c.size(), m - 1); i++)
                    t.pb(c[i]);
            t.resize(m);
            bob(t);
        }
    }

    while(decomp() > m + 1){
        if(vect[0].size() == m) bob(vect[0]);
        else if(vect[0].size() >= m + 2) even(vect[0]);
        else{
            vector<int> t;
            for(auto& c : vect)
                for(int x : c) t.pb(x);
            t.resize(m);
            bob(t);
        }
    }

    return n - m - 1;
}

• 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