XOR 回路 (AOJ 2277)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2277

問題

略

解法

1が返ってくるまでランダムな列をクエリに投げる。1が返ってきたら後は2分探索すれば良い。2回目以降は動作していると分かっているビットには0を入れておくこと。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int n, k;
bool exist[10010];
bool target[10010];
char output[10010];

int Communicate() {
  printf("%s\n", output);
  fflush(stdout);
  int v;
  scanf("%d", &v);
  return v;
}

int UpdateTarget(int c) {
  int index = -1;
  REP(i, n) {
    if (!target[i]) { continue; }
    if (output[i + 1] == '0' + c) { target[i] = false; }
    if (index == -2 || !target[i]) { continue; }
    else if (index == -1) { index = i; }
    else { index = -2; }
  }
  assert(index != -1);
  return index;
}

void RandomSequence() {
  output[0] = '?';
  REP(i, n) {
    if (!target[i]) { output[i + 1] = '0'; }
    else { output[i + 1] = '0' + (rand() % 2 ? 1 : 0); }
  }
  output[n + 1] = '\0';
}

int main() {
  scanf("%d %d", &n, &k);
  MEMSET(exist, false);
  REP(i, k) {
    REP(j, n) { target[j] = !exist[j]; }
    while (true) {
      RandomSequence();
      if (Communicate()) { break; }
    }
    int prev = 0;
    while (true) {
      int index = UpdateTarget(prev);
      if (index >= 0) {
        exist[index] = true;
        break;
      }
      RandomSequence();
      prev = Communicate() == 0 ? 1 : 0;
    }
  }

  vector<int> ans;
  REP(i, n) { if (exist[i]) { ans.push_back(i + 1); } }
  printf("!");
  REP(i, k) {
    if (i != 0) {
      putchar(' ');
    }
    printf("%d", ans[i]);
  }
  puts("");
  fflush(stdout);
}