#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];
}
cout << count << i << endl;
}
}
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++;
}
}
}
}
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:213:1: warning: control reaches end of non-void function [-Wreturn-type]
213 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |