Skip to content

Interactive Problems

Interactive problems were already present in IOI last century. Although interactive problems have not appeared in provincial-level and below competitions in recent years, the NOI series in 2019 featured two interactive problems in a row: "P5208 [WC2019] I Jun's Shop" and "P5473 [NOI2019] I Jun's Adventure", which may indicate the return of interactive problems to the NOI series.

Interactive problems do not require high-level algorithmic prerequisites and generally have no strict time limits; the quality of a program often depends only on the interaction count limit. Therefore, when learning interactive problems, it is recommended to progress step by step in order of difficulty. If you intend to exercise algorithmic thinking rather than merely learning algorithms, solving interactive problems is an excellent method. Although interactive problems usually have lower requirements for algorithms already mastered by contestants, it is still recommended to have a certain level of advanced and provincial-level algorithmic knowledge before attempting interactive problems, as your algorithmic thinking and knowledge base will have reached a certain level by then. For a basic introduction to interactive problems, refer to OI Wiki's Problem Types - Interactive Problems.

Special errors in interactive problems:

  • Contestants must flush the buffer after each output; otherwise, an "Idleness limit exceeded" error will occur. Additionally, if the problem contains multiple test cases and the program can determine the answer before reading all data, it must still read all data; otherwise, an ILE will also occur due to input confusion (you can submit multiple queries at once and receive all answers at once). Also, try to avoid using fast input.
  • If the program makes too many queries, Codeforces will give a "Wrong Answer" verdict (though the judging system will explain the reason for the Wrong Answer), while UVa will give a "Protocol Limit Exceeded (PLE)" verdict.
  • If the program's interaction format is incorrect, UVa will give a "Protocol Violation (PV)" verdict.

Due to the cumbersome input and output in interactive problems, it is recommended to encapsulate input and output functions separately.

During competitions, if the problem author provides a grader header file (for debugging grader interactive problems) or a checker program (for debugging stdio interactive problems), debugging interactive problems becomes relatively simple, because testing interactive problems is much more difficult than testing ordinary problems. Without testlib.h, the stdio interaction library for problems with many interaction details typically has about 3k lines of code, plus a 3k-line testing program, requiring at least an hour to implement. However, regardless of whether debugging tools are available, debugging interactive problem code often requires contestants to simulate the interaction process with the program. Therefore, interactive problems require contestants to design high-quality programs, striving to get them right on the first try, while also possessing strong static error-checking abilities.

Example problems:

CF679A Bear and Prime 100

Each prime number has exactly two factors, so we can directly enumerate the factors of the number to guess. Since the limit is at most 20 queries, and for larger numbers (e.g., 92), attempting prime factorization reveals that we need to enumerate primes up to \(\lfloor\frac{n}{2}\rfloor\). Therefore, we first sieve primes within 50 and query all these numbers each time.

Since testing for this problem is relatively easy, we can try all numbers within the range. We will find that the program cannot effectively handle squares of primes. So we include the squares of 2, 3, 5, and 7: 4, 9, 25, 49, totaling 19 numbers, which meets the requirement.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <cstdio>
constexpr int prime[] = {2,  3,  4,  5,  7,  9,  11, 13, 17, 19,
                         23, 25, 29, 31, 37, 41, 43, 47, 49};
int cnt = 0;
char res[5];

int main() {
  for (int i : prime) {
    printf("%d\n", i);
    fflush(stdout);
    scanf("%s", res);
    if (res[0] == 'y' && ++cnt == 2) return printf("composite"), 0;
  }
  printf("prime");
  return 0;
}

CF843B Interactive LowerBound

The linked list has at most \(5 \times 10 ^ 4\) elements, but we can only query \(1999\) times and can only obtain the next element of a node, so the ordinary method of traversing the entire list is not feasible. The only way to approximate the target element's position is to randomly sample points.

For \(n < 2000\), we can directly enumerate. For \(n \ge 2000\), we randomly sample 1000 points. The expected distance between these points is small, so we can start traversing from the largest value less than \(x\). It can be proven that we will obtain the answer before reaching the next sampled point. During traversal, once we find an element greater than or equal to \(x\), we can directly output it.

Although the overall idea is simple, in practice, without knowledge of non-perfect random algorithms like simulated annealing, thinking about it might be more difficult.

Additionally, due to Codeforces' hack mechanism, many people deliberately target code without initialized random seeds, so we need srand((size_t)new char) before random_shuffle().

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <algorithm>
#include <cstdio>
#include <cstdlib>
constexpr int N = 50005;
int n, start, x;
int a[N];

int main() {
  scanf("%d%d%d", &n, &start, &x);
  if (n < 2000) {
    int ans = 2e9;
    for (int i = 1; i <= n; i++) {
      printf("? %d\n", i), fflush(stdout);
      int val, next;
      scanf("%d%d", &val, &next);
      if (val >= x) ans = std::min(ans, val);
    }
    if (ans == 2e9) ans = -1;
    printf("! %d", ans), fflush(stdout);
  } else {
    srand((size_t) new char);
    int p = start, ans = 0;
    for (int i = 1; i <= n; i++) a[i] = i;
    std::random_shuffle(a + 1, a + n + 1);
    for (int i = 1; i <= 1000; i++) {
      printf("? %d\n", a[i]), fflush(stdout);
      int val, next;
      scanf("%d%d", &val, &next);
      if (val < x && val > ans) p = a[i], ans = val;
    }
    while (p != -1 && ans < x) {
      printf("? %d\n", p), fflush(stdout);
      int val, next;
      scanf("%d%d", &val, &next);
      ans = val;
      p = next;
    }
    if (ans < x) ans = -1;
    printf("! %d", ans), fflush(stdout);
  }
  return 0;
}

UOJ206 [APIO2016] Gap

Discuss two subtasks:

  1. Query count limit.

    Consider the first query. Since we initially know nothing, we need to query the range \([1, 10 ^ {18}]\) to obtain the minimum and maximum values.

    Since the query limit is exactly \(\frac{N + 1}{2}\), consider how to obtain previously unacquired values each time, so as to acquire all numbers in the sequence within the limit. The method is simple: after each query \([s, t]\), let the obtained values be \(mn, mx\); then the next query is \([mn + 1, mx - 1]\).

  2. Query interval size limit.

    Since the problem requires that the total number of numbers in queried intervals does not exceed \(3N\), consider minimizing the query intervals. The above method is no longer usable because the total number of numbers in queried intervals scales as \(O(N ^ 2)\). We can consider binary search on the value range, but this method is not reliable, as the worst case might be \(O(N ^ 2)\). So we need a more efficient way to partition the value range, avoiding repeated queries of points within query intervals and wasting opportunities.

    Considering that the answer will not be less than \(\lfloor\frac{a_n - a_1}{N - 1}\rfloor\), we can partition the value range by this value. Let \(i\) start at 0, \(ans\) start at the above value. Each time query \([i, i + ans]\) and update \(ans\), then increment \(i\) by \(ans\).

    However, this method also does not work well for subtask 1, because in the worst case many queries might contain no numbers in their value range.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <algorithm>
#include <cstdio>

#include "gap.h"

long long findGap(int T, int N) {
  static long long a[100005] = {}, ans = 0;
  long long s = 0, t = 1e18, s1, t1;
  if (T == 1) {
    int l = 1, r = N;
    while (l <= r) {
      MinMax(s, t, &s1, &t1);
      a[l++] = s1, a[r--] = t1;
      s = s1 + 1, t = t1 - 1;
    }
    for (int i = 2; i <= N; i++) ans = std::max(ans, a[i] - a[i - 1]);
  } else if (T == 2) {
    MinMax(s, t, &s1, &t1);
    ans = (t1 - s1) / (N - 1);
    long long l = s1 + 1, r = t1, last = s1;
    for (long long i = l; i <= r;) {
      MinMax(i, i + ans, &s1, &t1);
      i += ans + 1;
      if (s1 != -1) ans = std::max(ans, s1 - last), last = t1;
    }
  }
  return ans;
}

CF750F New Year and Finding Roots

Given the strict requirements \(h \le 7\) and query count \(\le 16\), we need to maximize the use of information obtained from queries very strictly.

For \(h \le 4\), we can directly brute force. However, for \(h > 4\), we need an efficient traversal algorithm.

Random sampling is not a good method because we cannot determine if we are close enough to the root, and even excluding repeated sampling, the probability of hitting the root at least once is \(1 - (\frac{2 ^ h - 2}{2 ^ h - 1})\), which is still very small.

Since \(1 \le k \le 3\), and we do not know which direction is closer to the root, we consider the worst case: if \(k = 3\), the first two traversal directions are away from the root, and the third is toward the root. So we must traverse in all three directions.

Consider both bfs and dfs traversal methods. Since the bfs search tree might be large, we prioritize dfs. Of course, if we know the current depth and the search tree size within the depth range is less than or equal to the remaining queries, we can directly use bfs.

Knowing the current node's depth and the current traversal direction provides a significant advantage. However, knowing whether we are moving toward the root or toward a leaf is very difficult. When using dfs, we only know the direction when we reach the root (\(k = 2\)) or a leaf (\(k = 1\)). So we need to know the current node's depth as much as possible and cannot use methods like iterative deepening search, stopping midway.

Consider randomly selecting an initial node; starting from it might encounter the worst case described above.

If \(k = 1\), we directly know the current node's depth.

If \(k = 2\), the current node is the root.

If \(k = 3\), we directly dfs in three directions. Considering that two directions are directly toward leaves, the traversal path lengths are the same; the other direction is toward the root, but we might accidentally go toward a leaf, resulting in a longer traversal path. At this point, we can calculate the current node's depth.

When \(k = 1\) or \(k = 3\), we need to consider longer traversal paths. We can find the node with the minimum depth on the path (which must be shallower than the initial node). If we mark visited nodes and avoid revisiting, only one traversal path remains from that node. Although this path might still lead to a leaf, it also necessarily contains a node shallower than the starting point, from which we can repeat the above steps.

Of course, considering the worst case for \(h = 7\) (each step toward the root is immediately followed by a step toward a leaf), we find that if we only use dfs, we need at worst \(\frac{(1 + 7) \times 7}{2} = 28\) queries. However, we already know the initial node's depth, so we can calculate the depths of all visited nodes and, based on our earlier discussion about bfs, decide whether we can directly bfs from the shallowest node.

At this point, we can calculate that at worst we need 17 queries. So we consider removing one node from the search tree (due to dfs's blind traversal nature, we consider bfs): when performing bfs of depth \(k\), the search tree has at worst \(2 ^ k - 1\) nodes, possibly requiring \(2 ^ k - 1\) queries to determine which node has exactly 2 neighbors. However, if we have already queried \(2 ^ k - 2\) of them, we know the last node must be the root.

The optimal solution in the worst case is: for \(h = 7\), start dfs from a leaf, each time taking only one step toward the root before immediately going toward a leaf. After 10 queries, the current known shallowest node depth is 4. Since its parent is known, directly start bfs from its parent (search tree depth 3, node count \(2 ^ 3 - 1 = 7\)). During bfs, after querying \(2 ^ 3 - 2 = 6\) times, determine that the last node in the bfs search tree is the root.

Our algorithm can exactly hit the worst-case limit of 16 queries.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
constexpr int N = 256 + 5;
int T, h, chance;
bool ok;
vector<int> to[N], path;

bool read(int x) {
  if (to[x].empty()) {
    printf("? %d\n", x), fflush(stdout);
    int k, t;
    scanf("%d", &k);
    if (k == 0) exit(0);
    for (int i = 0; i < k; i++) {
      scanf("%d", &t);
      to[x].push_back(t);
    }
    if (k == 2) {
      printf("! %d\n", x), fflush(stdout);
      return ok = true;
    }
    chance--;
  }
  return false;
}

bool dfs(int x) {
  if (to[x].empty()) path.push_back(x);
  if (read(x)) return true;
  for (int i : to[x])
    if (to[i].empty()) return dfs(i);
  return false;
}

void bfs(int s, int k) {
  queue<int> q;
  for (int i : to[s])
    if (to[i].empty()) q.push(i);
  for (int i = 1; i < k; i++) {
    int x = q.front();
    q.pop();
    if (read(x)) return;
    for (int j : to[x])
      if (to[j].empty()) q.push(j);
  }
  for (int i = 1; i < k; i++) {
    int x = q.front();
    q.pop();
    if (read(x)) return;
  }
  printf("! %d\n", q.front()), fflush(stdout);
}

int main() {
  for (scanf("%d", &T); T--;) {
    ok = false;
    for (int i = 0; i < N; i++) to[i].clear();
    chance = 16;
    scanf("%d", &h);
    if (h == 0) exit(0);
    vector<int> long_path;
    if (read(1)) continue;
    int root, dep;
    if (to[1].size() == 1)
      root = 1, dep = h;
    else {
      for (int i : to[1]) {
        path.clear();
        if (dfs(i)) break;
        if (path.size() > long_path.size()) swap(path, long_path);
      }
      if (ok) continue;
      dep = h - (path.size() + long_path.size()) / 2;
      root = long_path.at((long_path.size() - (h - dep)) - 1);
    }
    while ((1 << (dep - 1)) - 2 > chance) {
      path.clear();
      if (dfs(root)) break;
      dep = h - (h - dep + path.size()) / 2;
      root = path.at((path.size() - (h - dep)) - 1);
    }
    if (!ok) bfs(root, 1 << (dep - 2));
  }
  return 0;
}

UVa12731 Mysterious Space Station

Since the only feedback is whether moving causes a collision, we should consider walking as close to walls as possible without getting lost. This has several advantages:

  • When walking near walls, it is easy to know if we will collide, obtaining as much information as possible.
  • Cells adjacent to walls are not teleporter cells, avoiding the robot getting lost.

So, if we know the robot might be at a certain position near a wall, to confirm whether the robot is indeed there, we can use the "wall-following" method to determine if we are really at that position. According to topology principles, in a maze with walls on both sides, if we enter from the entrance and always keep one hand on the same wall, we can guarantee finding the exit. Since the walls in this problem are closed, simply following the path along the walls ensures we can return to the starting point without colliding. Additionally, since the wall-adjacent path is the largest closed loop on the map, we don't need to deliberately collide to keep the robot near walls in the code; we can mark the wall-adjacent path on the map. Moreover, once we collide, we need to quickly backtrack along the original path, reducing steps while avoiding getting lost.

From the above, we can infer a trial-and-error method to determine if the robot is at a specific cell: move the robot to the wall-adjacent path without stepping into unknown cells or known teleporters, then walk around the wall-adjacent path once. If no collision occurs during this process, we can confirm the robot is indeed at the specific cell.

We can use the above method: initially mark all unknown cells on the map, then check each unknown cell from top to bottom, left to right to see if it is a teleporter. First move above the unknown cell, then move down and left. Then use the above method to check if the robot is to the left of the unknown cell. If not, the robot is not where it should be, meaning the unknown cell is a teleporter.

After identifying unknown cells, we need to determine the pairing relationships among the 2k unknown cells. The actual method is simple: just brute-force pairing. Since \(k \le 5\), at most \(9 + 7 + 5 + 3\) trial-and-error attempts are needed. In contrast, checking all unknown cells on the map requires at most \(121 - 40\) trial-and-error attempts.

Currently, the following code can only pass the UOJ mirror problem: #247. "Rujia Liu's Present 7" Mysterious Space Station, but not the original UVa problem. After modifying Liu Rujia's reference solution on UOJ, it still cannot pass, and we cannot contact Liu Rujia for now. Therefore, the following code is based on UOJ.

However, Liu Rujia's reference solution is of much higher quality than the code below. You can view the reference solution that passed the UOJ mirror problem. On the same data, the reference solution uses very few moves.

Reference Code 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>

#define Wall 0
#define Unknown 1
#define Space 2
#define Gate 3
#define Path 4

const int N = 20;
const int dir[8][2] = {{0, 1},  {1, 0}, {0, -1}, {-1, 0},
                       {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
const char dirs[5] = "ESWN";
int n, m, k;
int a[N][N], id[N][N];

struct point {
  int x, y;

  point(int x = 0, int y = 0) : x(x), y(y) {}

  bool operator==(const point& tmp) const { return x == tmp.x && y == tmp.y; }

  bool operator!=(const point& tmp) const { return !(*this == tmp); }

  point side(int d) const { return point(x + dir[d][0], y + dir[d][1]); }

  int check(int d) { return a[x + dir[d][0]][y + dir[d][1]]; }

  int id() { return ::id[x][y]; }
} start;

std::vector<std::pair<point, int>> path;
std::pair<point, point> ans[N];
std::pair<point, bool> vis[N];

bool walk(int d) {
  printf("MoveRobot %c\n", dirs[d]);
  fflush(stdout);
  int ret;
  scanf("%d", &ret);
  return ret;
}

bool walk(int d, std::stack<int>& st) {
  if (walk(d)) {
    st.push(d);
    return true;
  }
  return false;
}

bool read() {
  if (scanf("%d%d%d", &n, &m, &k) != 3) return false;
  if (n == 0) return false;
  memset(a, 0, sizeof(a));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      char c;
      std::cin >> c;
      if (c == 'S') start = point(i, j);
      if (c == '*')
        a[i][j] = Wall;
      else
        a[i][j] = Unknown;
    }
  return true;
}

void answer() {
  for (int i = 0; i < k; i++)
    printf("Answer %d %d\n", ans[i].first.id(), ans[i].second.id());
  fflush(stdout);
}

// Wall-following method. Since the Path along walls is a maximal closed loop,
// we only need to ensure no obstacles are encountered while following the Path.
void wall_follower_init(point x, int last, int wallside, point s) {
  if (x == s && !path.empty()) return;
  if (x.check(wallside) == Path) {
    path.push_back(std::make_pair(x, wallside));
    wall_follower_init(x.side(wallside), wallside, last ^ 2, s);
  } else if (x.check(last) == Wall) {
    for (int i = 0; i < 4; i++)
      if (i != (last ^ 2) && x.check(i) != Wall) {
        path.push_back(std::make_pair(x, i));
        wall_follower_init(x.side(i), i, last, s);
        return;
      }
  } else {
    path.push_back(std::make_pair(x, last));
    wall_follower_init(x.side(last), last, wallside, s);
  }
}

void init() {
  int cnt = 1;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      if (a[i][j] == Unknown) {
        id[i][j] = cnt++;
        for (int k = 0; k < 8; k++)
          if (point(i, j).check(k) == Wall) {
            a[i][j] = Path;
            break;
          }
      } else
        id[i][j] = 0;
    }
  path.clear();
  int wallside = 0, last = 0;
  for (int i = 0; i < 4; i++)
    if (start.check(i) == Wall) {
      wallside = i;
      break;
    }
  for (int i = 0; i < 4; i++)
    if (start.check(i) == Path && i != (wallside ^ 2)) {
      last = i;
      break;
    }
  wall_follower_init(start, last, wallside, start);
}

void undo(std::stack<int>& st) {
  while (!st.empty()) walk(st.top() ^ 2), st.pop();
}

bool wall_follower(point x) {
  std::stack<int> st;
  bool ok = true;
  int i = 0;
  while (i < path.size() && path[i].first != x) i++;
  for (int j = i; ok && j < path.size(); j++) {
    if (walk(path[j].second))
      st.push(path[j].second);
    else
      ok = false;
  }
  for (int j = 0; ok && j < i; j++) {
    if (walk(path[j].second))
      st.push(path[j].second);
    else
      ok = false;
  }
  if (!ok) undo(st);
  return ok;
}

// Determine if we are currently at x using a "crossing the river by feeling the stones" method.
// Simply move in directions that avoid obstacles, unknown cells, and teleporters to reach Path.
// Used when finding teleporters and pairing teleporters.
void bfs(point s, point t, std::vector<int>& v) {
  static int map[N][N] = {};
  memset(map, -1, sizeof(map));
  std::queue<point> q;
  map[s.x][s.y] = 4;
  q.push(s);
  while (!q.empty()) {
    point x = q.front();
    q.pop();
    if (x == t) break;
    for (int i = 0; i < 4; i++) {
      point y = x.side(i);
      if ((x.check(i) == Path || x.check(i) == Space) && map[y.x][y.y] == -1) {
        map[y.x][y.y] = i;
        q.push(y);
      }
    }
  }
  for (point x = t; x != s; x = x.side(map[x.x][x.y] ^ 2)) {
    v.push_back(map[x.x][x.y]);
  }
  std::reverse(v.begin(), v.end());
}

bool move(point s, point t, std::stack<int>& st) {  // Used when approaching teleporters
  static std::vector<int> v;
  v.clear();
  bfs(s, t, v);
  for (int i : v)
    if (!walk(i, st)) return false;
  return true;
}

// Move to the wall as quickly as possible
bool make_sure(point x, int last) {
  if (a[x.x][x.y] == Path) return wall_follower(x);
  for (int i = 0; i < 4; i++)
    if ((x.check(i) == Path || x.check(i) == Space) && i != (last ^ 2)) {
      if (!walk(i)) return false;
      bool ret = make_sure(x.side(i), i);
      walk(i ^ 2);
      return ret;
    }
  return false;
}

void find_gate() {
  int cnt = 0;
  std::stack<int> st;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      if (cnt == k * 2 && a[i][j] == Unknown)
        a[i][j] = Space;
      else if (a[i][j] == Unknown) {
        bool ok = true;
        if (!move(start, point(i - 1, j), st))
          ok = false;
        else if (!walk(1, st))
          ok = false;
        else if (!walk(2, st))
          ok = false;
        else if (!make_sure(point(i, j - 1), -1))
          ok = false;
        if (!ok) {
          vis[cnt++] = std::make_pair(point(i, j), false);
          a[i][j] = Gate;
          for (int k = 0; k < 8; k++) {
            point y = point(i, j).side(k);
            if (point(i, j).check(k) == Unknown) a[y.x][y.y] = Space;
          }
        } else
          a[i][j] = Space;
        undo(st);
      }
}

void make_gate_pair() {
  int cnt = 0;
  std::stack<int> st;
  for (int i = 0; i < k * 2; i++)
    if (!vis[i].second)
      for (int j = 0; !vis[i].second && j < k * 2; j++)
        if (j != i && !vis[j].second) {
          bool ok = true;
          if (!move(start, vis[i].first.side(2), st))
            ok = false;
          else if (!walk(0, st))
            ok = false;
          else if (!make_sure(vis[j].first.side(0), -1))
            ok = false;
          if (ok) {
            ans[cnt++] = std::make_pair(vis[i].first, vis[j].first);
            vis[i].second = vis[j].second = true;
          }
          undo(st);
        }
}

int main() {
  while (read()) {
    init();
    find_gate();
    make_gate_pair();
    answer();
  }
  return 0;
}

Exercises

References and Further Reading

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用