Codeforces Round #670 DIV2 E問題 - Deleting Numbers

Source

Codeforces Round #670 DIV2 E問題 (2750pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20200913-1）のコード

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

//interactive
int N;
int ps, p[1d5];
int sz, arr[1d5+1];
int cs, cand[1d5];

void dodel(int k){
  rep(i,k,N+1,k) sz -= arr[i], arr[i] = 0;
}
int doget(int k){
  int res = 0;
  rep(i,k,N+1,k) res += arr[i];
  return res;
}
int queryA(int k){
  wt("A", k);
  return rd_int();
}
int queryB(int k){
  dodel(k);
  wt("B", k);
  return rd_int();
}

{
  int i, j, k, res = 1, b = 100, st, ed;
  rd(N);
  if(N==1) wt("C", 1), return 0;

  ps = Prime(N+1, p);
  rep(i,1,N+1) sz++, arr[i] = 1;

  rep(i,ps){
    if((ll) p[i] * p[i] > N) break;
    queryB(p[i]);
  }
  k = queryA(1);

  if(k == sz){
    rep(i,ps){
      if((ll) p[i] * p[i] <= N) continue;
      cand[cs++] = p[i];
    }
    rep(st,0,cs,b){
      ed = min(st + b, cs);
      rep(i,st,ed) queryB(cand[i]);
      k = queryA(1);
      if(k == sz) continue;
      rep(i,st,ed) if(queryA(cand[i]) == 1) res = cand[i], break_break;
    }
  } else {
    rep(i,ps){
      j = 1;
      while( (ll)j*p[i] <= N ){
        if(doget(j*p[i]) == queryA(j*p[i])) break;
        j *= p[i];
      }
      res *= j;
    }
  }

  wt("C", res);
}

Current time: 2024年04月20日16時16分29秒
Last modified: 2020年09月13日14時09分52秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF670 CF_Div2_E
トップページに戻る

Logged in as: unknown user (not login)