Submission #1205911

#TimeUsernameProblemLanguageResultExecution timeMemory
1205911bronze_coderPermutation Game (APIO25_permgame)C++20
46 / 100
9 ms328 KiB
#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]; } } } 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++; } } } } else{ 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; for(int i:s){ if(i<0){ total -= i; } } if(total==m){ best = n-m+1; while(ans<best){ vector<int> visited(n,0); vector<int> query(m); int count = 0; for(int i=0;i<n;i++){ if(visited[i]==0&&s[i]<-1){ int j = i; while(visited[j]==0){ visited[j] = 1; query[order[count]] = j; j = p[j]; count++; } } } 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++; } } } } else{ best = n-m-1; 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<int> query(m); int y = 0; for(int i=0;i<n;i++){ if(s[i]==-m){ int j = i; for(int z=0;z<m;z++){ query[order[z]] = j; j = p[j]; y = 1; } break; } } if(y==0){ for(int i=0;i<n;i++){ if(s[i]<=-m-2&&s[i]!=-m-3){ int j = i; for(int z=0;z<m;z++){ query[order[z]] = j; j = p[j]; if(z==m-2){ j = p[j]; } y = 1; } break; } } } if(y==0){ for(int i=0;i<n;i++){ if(s[i]==-m-3){ vector<int> o; int j = i; o.push_back(j); j = p[j]; while(j!=i){ o.push_back(j); j = p[j]; } for(int z=0;z<m;z++){ if(z<m/2){ query[order[z]] = o[2*z+z%2]; } else if(m%4==0){ query[order[z]] = o[m-1-2*(z-m/2)-(z-m/2+1)%2]; } else{ query[order[z]] = o[m-1-2*(z-m/2)-(z-m/2)%2]; } } y = 1; break; } } } if(y==0){ vector<pair<int,int>> c; for(int i=0;i<n;i++){ c.push_back({-s[i],i}); } sort(c.begin(),c.end()); int count = 0; vector<int> visited(n,0); for(int i=c.size()-1;i>=0;i--){ int j = c[i].second; while(count<m&&visited[j]==0){ query[order[count]] = j; j = p[j]; count++; } } } 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:365:1: warning: control reaches end of non-void function [-Wreturn-type]
  365 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...