Solution - Codeforces 1190C Tokitsukaze and Duel

考虑到两人对应的操作是相同的，于是可以从对称的角度来思考。

考虑到在先手做出操作后，后手一个较为特殊的操作是不做任何影响，也就是重复先手的操作。
能够发现如果对于后手这不能必胜，那么他一定不会去产生影响，并又把这个局面留给先手，相当于是先后手的交换。
对于先手又是同样的，因为两人操作相同，对于他也是不必胜的，那么他也会重复操作留给后手，那么就平局了。

于是能够知道的是，如果初始状态就能必胜，那么先手必胜。
否则如果无论先手怎样操作，后手都能必胜的话，后手必胜。
否则就是先手存在一种方式，使得操作后后手不能必胜，那么两人就会一直重复第一次的操作，最终平局。

对于判断，可以提前预处理好前缀同色段的长度与后缀连续段的长度。
通过分讨操作所在的段的左右两方的是否同色，长度与 \(k\) 的大小关系，以及 \(s_1, s_n\) 的相等关系即可判断得出先 / 后手是否必赢。

时间复杂度 \(\mathcal{O}(n)\)。

#include<bits/stdc++.h>
constexpr int maxn = 1e5 + 10;
int n, k;
char s[maxn];
bool f[maxn], g[maxn];
int main() {
   scanf("%d%d%s", &n, &k, s + 1);
   f[0] = true;
   for (int i = 1; i <= n; i++) {
      f[i] = f[i - 1] && (s[i] == s[1]);
   }
   g[n + 1] = true;
   for (int i = n; i; i--) {
      g[i] = g[i + 1] && (s[i] == s[n]);
   }
   if (f[n - k] || g[k + 1]) {
      return puts("tokitsukaze"), 0;
   }
   for (int l = 1, r = k; r <= n; l++, r++) {
      if (f[l - 1] && g[r + 1] && s[1] == s[n]) {
         return puts("tokitsukaze"), 0;
      }
   }
   bool fl = true;
   for (int l = 1, r = k; r <= n; l++, r++) {
      for (char c : {'0', '1'}) {
         bool gl = l > 1 && (! f[l - 1] || c != s[1]);
         bool gr = r < n && (! g[r + 1] || c != s[n]);
         if ((gl && gr) || (gl && l - 1 > k) || (gr && n - r > k)) {
            fl = false;
            break;
         }
      }
   }
   puts(fl ? "quailty" : "once again");
   return 0;
}