[ABC313] D - Odd or Even

[Q]https://atcoder.jp/contests/abc313/tasks/abc313_d
いてえ結果でした。80分あがいてWAでした。

考察
・K=1のとき
?1, ?2, …, ?Nで
で簡単に特定できると思う。

・とりあえずN通りの条件式を用意したい。
Q. K要素の連番を質問してみる。
?123
?234
?345…
とする場合はどうだろう？
A. ダメケースが存在する。

N=6, K=3の場合を考える。
? 1 2 3
?   2 3 4
?     3 4 5
?       4 5 6
? 1       5 6
? 1 2       6

これでわかる関係は、
(123) - (234) = 1-4の関係
(234) - (345) = 2-5の関係
(345) - (456) = 3-6の関係
(456) - (561) = 4-1の関係 <= すでに1つ目の調査で得られている。

つまり、NとKが互いに素でない場合に、閉路情報で無駄遣いしてしまうことになる。

NとKが互いに素な場合はACを得られる。
大半のケースで通るため、逆に厄介であった。この発想を捨てて転換しなきゃいけない。

Q. 解説を見る
次の2通りに分けるようだ。
1. まず、1~K+1までの要素を確定させる。質問はK+1回。総和を利用する。
2. 次に、K+2以降の値を個別に確定させる。

N=6, K=3の場合
1. まず1~4までの要素を個別に確定させる。

クエリは以下の4通りを聞く。
? 1 2 3
?   2 3 4
? 1   3 4
? 1 2   4

すると、それぞれの要素をK回ずつ利用しているのがわかる。
そのため、総和の偶奇は、
? 1 2 3 4 
と等しくなる。

これがわかるので、
(1234) - (123) = 4の情報
(1234) - (234) = 1の情報
(1234) - (134) = 2の情報
(1234) - (124) = 3の情報
を確定できた。

2. 次に、12の情報がわかっているので、
? 1 2 5
? 1 2   6
をしてしまえば、
(125) - (12) = 5の情報
(126) - (12) = 6の情報
が得られる。

実装

void query(vector<ll> &A) {
  cout << "? ";
  ll n = A.size();
  rep(i, n) { cout << (A[i] + 1) << " \n"[i == n - 1]; }
}
void answer(vector<ll> &A) {
  cout << "! ";
  ll n = A.size();
  rep(i, n) { cout << A[i] << " \n"[i == n - 1]; }
}

int main() {
  cincout();
 
  ll N, K;
  cin >> N >> K;
  vector<ll> ans(N);
  vector<ll> ret(N);
 
  // まず1~K+1までを確定。
  // そのあと、K+2~Nまでを確定。

  // まず?123 ?234 ?341 ?412で1234を確定
  ll sum = 0;
  rep(i, K + 1) {
    vector<ll> A(K);
    rep(j, K) { A[j] = (i + j) % (K + 1); }
    query(A);
    cin >> ret[i];
    sum ^= ret[i];
  }
  rep(i, K + 1) { ans[(K + i) % (K + 1)] = sum ^ ret[i]; }
  // 次に?12を取得
  ll base = 0;
  rep(i, K - 1) base ^= ans[i];
  // 最後に?125, ?126
  for (ll i = K + 1; i < N; ++i) {
    vector<ll> A(K);
    rep(j, K - 1) A[j] = j;
    A[K - 1] = i;
    query(A);
    cin >> ret[i];
    ans[i] = ret[i] ^ base;
  }
  answer(ans);
}

https://atcoder.jp/contests/abc313/submissions/44311804