技術室奥プログラミングコンテスト#4 Day1 M問題 - Pakenのうさぎ

Source

技術室奥プログラミングコンテスト#4 Day1
問題文

問題概要

省略

解法

省略

cLay（version 20190902-1）のコード

C++に変換後のコードはこちら

int N;

int K, A[6000];

int query(void){
  int i;
  char buf[10];

  if(K<=1) return 0;
  
  sort(A,A+K);
  printf("? %d", K);
  rep(i,K) printf(" %d", A[i]+1);
  printf("\n");
  fflush(stdout);
  scanf("%s",buf);
  if(buf[0]=='R') return 1;
  return 0;
}

void answer(int x, int y){
  if(x > y) swap(x, y);
  printf("! %d %d\n", x+1, y+1);
  fflush(stdout);
}


int mode;
int Xs, X[6000], Ys, Y[6000];
int Zs, Z[6000];

{
  int i, j, k, n, s;

  scanf("%d",&N);
  rep(i,N) X[Xs++] = i;

  for(;;){
    if(mode==0){
      if(Xs==2){
        answer(X[0], X[1]);
        break;
      }

      if(Xs > 4000) s = 2Xs/3; else s = Xs/2;

      K = 0;
      rep(i,s) A[K++] = X[i];
      k = query();
      if(k==1){
        Xs = s;
        continue;
      }

      K = 0;
      rep(i,s,Xs) A[K++] = X[i];
      k = query();
      if(k==1){
        Xs = K;
        rep(i,Xs) X[i] = A[i];
      } else {
        Ys = K;
        rep(i,Ys) Y[i] = A[i];
        Xs -= K;
        mode = 1;
      }
    } else {
      if(Xs==1 && Ys==1){
        answer(X[0], Y[0]);
        break;
      }

      if(Xs < Ys){
        Zs = Ys;
        rep(i,Zs) Z[i] = Y[i];
        Ys = Xs;
        rep(i,Ys) Y[i] = X[i];
        Xs = Zs;
        rep(i,Xs) X[i] = Z[i];
      }

      s = Xs / 2;
      K = 0;
      rep(i,s) A[K++] = X[i];
      rep(i,Ys) A[K++] = Y[i];
      k = query();
      if(k){
        Xs = s;
      } else {
        j = 0;
        rep(i,s,Xs) X[j++] = X[i];
        Xs = j;
      }
    }
  }
}

Current time: 2024年04月23日18時34分02秒
Last modified: 2019年09月04日00時13分00秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)