# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1205911 | bronze_coder | Permutation Game (APIO25_permgame) | C++20 | 9 ms | 328 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)
# | 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... |