Submission #1248578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248578		yoyoyoxx	Permutation Game (APIO25_permgame)	C++20	Compilation error	0 ms	0 KiB

permgame

#include <bits/stdc++.h>

using namespace std;

int bob(vector<int> t);  // provided

int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {

  vector<int> pos(n);

  for (int i = 0; i < n; i++) {

    pos[p[i]] = i;

  }

  int current = 0;

  for (int i = 0; i < n; i++) {

    if (p[i] == i) current++;

  }

  int k = n - m + 1;

  if (current >= k) return current;

  // Play to increase to k

  // For general, we attempt to fix from high to low.

  for (int v = n - 1; v >= 0; v--) {

    if (p[v] == v) continue;

    int b = pos[v];

    // Construct t to swap v and b

    vector<int> t(m, -1);

    // Find an adjacent pair

    int x = 0, y = 1;  // assume vertices 0 and 1 are adjacent, general find one.

    bool found = false;

    for (int j = 0; j < e; j++) {

      x = u[j];

      y = v[j];

      break;

    }

    t[x] = v;

    t[y] = b;

    // Fill other with distinct positions

    set<int> used;

    used.insert(v);

    used.insert(b);

    vector<int> available;

    for (int i = 0; i < n; i++) {

      if (used.count(i) == 0) available.push_back(i);

    }

    int idx = 0;

    for (int z = 0; z < m; z++) {

      if (t[z] == -1) {

        t[z] = available[idx % available.size()];

        idx++;

      }

    }

    // Ensure distinct

    set<int> check;

    for (int z = 0; z < m; z++) {

      if (check.count(t[z]) ) {

        // if not distinct, adjust

        // for simplicity, assume n large enough.

      }

      check.insert(t[z]);

    }

    // Call bob

    int j = bob(t);

    int p1 = t[u[j]];

    int p2 = t[v[j]];

    swap(p[p1], p[p2]);

    swap(pos[p[p1]], pos[p[p2]]);

    // Now, check current

    current = 0;

    for (int i = 0; i < n; i++) {

      if (p[i] == i) current++;

    }

    if (current >= k) break;

  }

  return k;

}

Compilation message (stderr)

permgame.cpp: In function 'int Alice(int, int, std::vector<int>, std::vector<int>, int, std::vector<int>)':
permgame.cpp:53:12: error: invalid types 'int[int]' for array subscript
   53 |       y = v[j];
      |            ^
permgame.cpp:117:17: error: invalid types 'int[int]' for array subscript
  117 |     int p2 = t[v[j]];
      |                 ^