国庆第五天

// NWERC2020 I Island Tour
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a); i <= (int)(b); ++i)
const int NN = 404;
int N, D[NN], T[4][NN];
// C[a,b,i,j] 人(a,b)分别从(i,j)出发会冲突吗?
bool C[4][4][NN][NN];
bool check(int p1, int p2, int s1, int s2) {
  	  // p1从s1开始，p2从s2开始会冲突吗?
  	  assert(p1 != p2);
 	  if (s1 == s2) return true;
  	  vector<int> A(N + 1), B(N + 1);
  	  // A[i]: p1到达i的时间，B[i], p1从i离开的时间
    for (int t = 0, i = 1; i <= N; i++) {  // 模拟p1的过程
      A[s1] = t, B[s1] = A[s1] + T[p1][s1], t = B[s1] + D[s1];  // 到下一站
      if (++s1 == N + 1) s1 = 1;
  }
    for (int t = 0, i = 1; i <= N; i++) {
    int a = t, b = t + T[p2][s2];  // p2到达和离开s2的时间
    if (max(a, A[s2]) < min(b, B[s2])) return true;  // 冲突
    t = b + D[s2];                                   // 到下一站
    if (++s2 == N + 1) s2 = 1;
  }
  return false;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> N;
  REP(i, 1, N) cin >> D[i];
  REP(p, 1, 3) REP(i, 1, N) cin >> T[p][i];
  REP(a, 1, 3) REP(b, a + 1, 3) REP(i, 1, N) REP(j, 1, N) {
    C[a][b][i][j] = check(a, b, i, j);
  }
  REP(i, 1, N) REP(j, 1, N) REP(k, 1, N) {  // i,j,k分别是三个人的起点
    if (!C[1][2][i][j] and !C[1][3][i][k] and !C[2][3][j][k])
      return printf("%d %d %d\n", i, j, k), 0;  // 两两都不冲突
  }
  return puts("impossible"), 0;
}
// AC 100

![](/media/202510/1_1759669439.png)
![](/media/202510/2_1759669424.png)