Submission #1207060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207060		Ludissey	Permutation Game (APIO25_permgame)	C++20	0 / 100	0 ms	328 KiB

permgame

#include "permgame.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

using namespace std;


int Alice(int m, int e, std::vector<int> u, std::vector<int> v, int n, std::vector<int> p) {
    std::vector<int> t(m);
    vector<int> pos(n);
    for (int i = 0; i < n; i++)
    {
        pos[p[i]]=i;
    }
    
    bool b=true;
    int k=1;
    while(b){
        b=false;
        vector<int> p2(n,0);
        for (int i = 0; i < n; i++) p2[i]=i;
        for (int i = 0; i < n; i++)
        {
            int x=i;
            vector<int> q;
            vector<int> visited(n,0);
            while(visited[x]==0&&sz(q)<3){
                visited[x]=k;
                if(sz(q)==2&&p[x]!=i) p2[pos[i]]=x;
                q.push_back(x);
                x=p[x];
            }
            if(x==i&&sz(q)==3){
                int j=Bob(q);
                swap(pos[p[q[u[j]]]],pos[p[q[v[j]]]]);
                swap(p[q[u[j]]],p[q[v[j]]]);
                b=true;
                break;
            }
        }
        if(!b){
            for (int i = 0; i < n; i++)
            {
                int x=i;
                vector<int> q;
                vector<int> visited(n,0);
                while(visited[x]==0&&sz(q)<3){
                    visited[x]=k;
                    q.push_back(x);
                    x=p2[x];
                }
                if(x==i&&sz(q)==3){
                    int j=Bob(q);
                    swap(pos[p[q[u[j]]]],pos[p[q[v[j]]]]);
                    swap(p[q[u[j]]],p[q[v[j]]]);
                    b=true;
                    break;
                }
            }
        }
        k++;
    }
    int sc=0;
    for (int i = 0; i < n; i++) sc+=(pos[p[i]]==p[i]);
    return sc;
}

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