Submission #1205385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205385		Mamedov	Permutation Game (APIO25_permgame)	C++20	46 / 100	24 ms	516 KiB

permgame

#include "permgame.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
#define iospeed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <typename T> void show(vector<T> &v) {
  for (T i : v) {
    cout << i << ' ';
  }
  cout << ln;
}

int getScore(int n, vi &p) {
  int score = 0;
  for (int i = 0; i < n; ++i) {
    if (p[i] == i) ++score;
  }
  return score;
}

vvi getCycles(int n, vi &p) {
  vvi cycles;
  vi vis(n, 0);
  for (int i = 0; i < n; ++i) {
    if (!vis[i]) {
      vi cycle;
      int node = i;
      while (!vis[node]) {
        vis[node] = 1;
        cycle.eb(node);
        node = p[node];
      }
      cycles.eb(cycle);
    }
  }
  sort(all(cycles), [&](vi &i, vi &j) {return i.size() > j.size();});
  return cycles;
}

int Alice(int m, int e, std::vector<int> u, std::vector<int> v, int n, std::vector<int> p) {
  int curScore = getScore(n, p);
  vvi g(m);
  for (int i = 0; i < e; ++i) {
    g[u[i]].eb(v[i]);
    g[v[i]].eb(u[i]);
  }
  
  int a = -1;
  for (int i = 0; i < m; ++i) {
    if (g[i].size() > 2) return curScore; // can't improve
    if (g[i].size() == 1) a = i; // end of chain 
  }
  vi ord;
  if (a == -1) a = 0; // cycle
  int b = -1;
  for (int i = 0; i < m; ++i) {
    ord.eb(a);
    int nxt = g[a][0];
    if (nxt == b) nxt = g[i][1];
    b = a;
    a = nxt;
  }

  int optimalScore;
  vi t(m);
  if (e == m - 1) {
    if (curScore >= n - (m - 1)) return curScore;
    optimalScore = n - (m - 1);
    if (m == 2) optimalScore = n;

    while (curScore < optimalScore) {
      vvi cycles = getCycles(n, p);
      int id = 0, pos = 0;
      for (int i = 0; i < m; ++i) {
        if (pos == size(cycles[id])) {
          pos = 0;
          ++id;
        }
        t[ord[i]] = cycles[id][pos++];
      }
      int j = Bob(t);
      swap(p[t[u[j]]], p[t[v[j]]]);
      curScore = getScore(n, p);
    }
  } else if (m == 3) {
    vvi cycles = getCycles(n, p);
    //for (auto c : cycles) show(c);
    int oddCycles = 0;
    for (auto c : cycles) if (c.size() % 2 == 1) ++oddCycles;
    //cerr << "oddCycles = " << oddCycles << ln;
    optimalScore = oddCycles;
    int ops = 0;
    while (curScore < optimalScore) {
      vi oddCycle;
      for (auto c : cycles) if (c.size() % 2 == 1) {
        oddCycle = c;
        break;
      }
      for (int i = 0; i < m; ++i) {
        t[ord[i]] = oddCycle[i];
      }
      int j = Bob(t);
      ++ops;
      assert(ops <= 3 * n);
      swap(p[t[u[j]]], p[t[v[j]]]);
      curScore = getScore(n, p);
    }
  } else if (m == 4) {
    if (curScore == n - 5 || curScore >= n - 3) return curScore;
    if (curScore == n - 4) optimalScore = n - 3;
    else optimalScore = n - 5;
    while (curScore < optimalScore) {
      vvi cycles = getCycles(n, p);
      int sz = cycles.size();
      if (cycles[0].size() >= 4) {
        for (int i = 0; i < m; ++i) {
          t[ord[i]] = cycles[0][i];
        }
        if (cycles[0].size() == 6) t[ord[m - 1]] = cycles[0][m];
      } else { // merge two cycles of size = 3 or size = 2
        if (cycles[0].size() == 3 && cycles[1].size() == 3) {
          for (int i = 0; i < m - 1; ++i) t[ord[i]] = cycles[0][i];
          t[ord[m - 1]] = cycles[1][0];
        } else {
          while (cycles[sz - 1].size() == 1) --sz;
          if (cycles[sz - 1].size() == 2 && cycles[sz - 2].size() == 2) {
            t[ord[0]] = cycles[sz - 1][0];
            t[ord[1]] = cycles[sz - 1][1];
            t[ord[2]] = cycles[sz - 2][0];
            t[ord[3]] = cycles[sz - 2][1];
          } else {
            assert(false);
          }
        }
      }
      int j = Bob(t);
      swap(p[t[u[j]]], p[t[v[j]]]);
      curScore = getScore(n, p);
    }
  }
  return optimalScore;
}

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