Submission #1291906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291906		LolkasMeep	Permutation Game (APIO25_permgame)	C++20	6 / 100	2 ms	348 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) {
    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 isLine = true;
    int end = 0;
    for(int i = 0; i < m; i++){
        if(deg[i] > 2) isLine = false;
        if(deg[i] == 1) end = i;
    }

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

    vector<int> line;
    if(isLine){
        for(int i = 0; i < line.size(); i++){
            cout << line[i] << ' '; 
        }
        cout << '\n';

        // assert(line.size() == m);

        cout << "built line \n";
    }

    // cout << "hi\n";
    while(true && isLine){
        // cout << "in loop\n";
        bool foundCycle = false;
        vector<bool> found(n, false);
        for(int i = 0; i < n && !foundCycle; 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';

            if(cycle.size() < line.size()) continue;
            foundCycle = true;

            // assert(cycle.size() >= 3);

            vector<int> t(line.size());

            for(int i = 0; i < line.size(); i++){
                t[i] = cycle[i];
            }

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

        if(!foundCycle) break;
    }

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

    return score;
}


int AliceB(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
    // cout << "hi\n";
    while(true){
        bool foundCycle = false;
        vector<bool> found(n, false);
        for(int i = 0; i < n && !foundCycle; 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';

            if(cycle.size() % 2 == 0) continue;
            foundCycle = true;

            assert(cycle.size() >= 3);

            vector<int> t = {cycle[0], cycle[1], cycle[2]};
            int j = Bob(t);
            swap(p[t[u[j]]], p[t[v[j]]]);
        }

        if(!foundCycle) break;
    }

    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: 6 / 6
• Subtask 3: 0 / 10
• Subtask 4: 0 / 24
• Subtask 5: 0 / 24
• Subtask 6: 0 / 30