제출 #1292269

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292269		LolkasMeep	Permutation Game (APIO25_permgame)	C++20	24 / 100	11 ms	524 KiB

permgame

#include "permgame.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
    assert(m == 4);

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

    // cout << "got degree\n";

    bool isLoop = true;
    for(int i = 0; i < m; i++){
        if(deg[i] > 2) isLoop = false;
    }

    // cout << "confirmed line " << end << '\n';

    vector<int> line;
    if(isLoop){
        int end = 0;
        line.push_back(end);
        int prev = -1;
        while(true){
            int next = end;
            for(const int &x : adjList[end]){
                if(x != prev) next = x;
            }
            if(next == 0) break;
            line.push_back(next);
            prev = end;
            end = next;
        }
    }

    // cout << "line: ";
    // for(int i = 0; i < line.size(); i++) cout << line[i] << ' ';
    // cout << '\n';


    while(true && isLoop){
        // cout << "in loop\n";
        vector<bool> found(n, false);
        vector<vector<int>> cycles;
        int cycleTotal = 0;

        for(int i = 0; i < n; i++){
            // cout << "checking: " << i << '\n';
            if(found[i]) continue;
            found[i] = true;
            if(i == p[i]) continue;

            vector<int> cycle;
            cycle.push_back(i);
            
            int index = i;
            while(p[index] != i){
                index = p[index];
                cycle.push_back(index);
                found[index] = true;
            }

            // cout << "found cycle: ";
            // for(const auto &x : cycle) cout << x << ", ";
            // cout << '\n';

            cycleTotal += cycle.size();
            cycles.push_back(cycle);

        }

        // cout << "cycles: ";
        // for(int i = 0; i < cycles.size(); i++) cout << cycles[i].size() << ' ';
        // cout << '\n'; 

        if(cycleTotal < line.size()) break;
        sort(cycles.begin(), cycles.end(), [](const vector<int> &a, const vector<int> &b){
            return a.size() > b.size();
        });

        vector<vector<int>> cycle2;
        vector<vector<int>> cycle3;
        
        for(int i = 0; i < cycles.size(); i++){
            if(cycles[i].size() == 2) cycle2.push_back(cycles[i]);
            if(cycles[i].size() == 3) cycle3.push_back(cycles[i]);
        }

        vector<int> t(line.size());
        // cout << "t: ";

        if(cycles[0].size() >= m){
            vector<int> cycle = cycles[0];
            if(cycle.size() % 2 == 1 || cycle.size() == 4){
                for(int i = 0; i < line.size(); i++){
                    t[line[i]] = cycle[i];
                }
            }else{
                assert(cycle.size() >= 6);
                for(int i = 0; i < line.size()-1; i++){
                    t[line[i]] = cycle[i];
                }
                t[line[line.size()-1]] = cycle[4];
            }
        }else{
            if(line.size() <= cycle2.size() * 2){
                int cycleI = 0;
                int cycleO = 0;
                for(int i = 0; i < line.size(); i++){
                    if(i - cycleO >= cycle2[cycleI].size()){
                        cycleO += cycle2[cycleI].size();
                        cycleI++;
                    }
                    t[line[i]] = cycle2[cycleI][i-cycleO];

                    // cout << t[i] << ' ';
                }
            }else if(line.size() <= cycle3.size() * 3){
                int cycleI = 0;
                int cycleO = 0;
                for(int i = 0; i < line.size(); i++){
                    if(i - cycleO >= cycle3[cycleI].size()){
                        cycleO += cycle3[cycleI].size();
                        cycleI++;
                    }
                    t[line[i]] = cycle3[cycleI][i-cycleO];

                    // cout << t[i] << ' ';
                }
            }else{
                // cout << "exiting\n";
                break;
            }
        }
        // cout << '\n';

        int j = Bob(t);
        swap(p[t[u[j]]], p[t[v[j]]]);
    }

    int score = 0;
    for(int i = 0; i < n; i++){
        if(i == p[i]) score++;
    }

    return score;
}

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