Submission #990078

#	Time	Username	Problem	Language	Result	Execution time	Memory
990078		canadavid1	Ancient Machine 2 (JOI23_ancient2)	C++17	22 / 100	113 ms	1560 KiB

ancient2

#include "ancient2.h"

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>


std::string Solve(int N) {
  // query one bit:
  // a[i], b[i] = i+1
  // a[b] = 1000
  // b[b] = 1001
  // a,b[1000] = 1000
  // a,b[1001] = 1001
  int Np = ((N+2)/3)*2+2;
  std::vector<int> a(Np+2);
  std::iota(a.begin(),a.begin()+Np,1);
  a[Np] = Np;
  a[Np+1] = Np+1;
  auto b = a;
  std::string s;
  std::string sb;
  for(int i = 0; i < Np; i++)
  {
    a[i] = Np;
    b[i] = Np+1;
    s.push_back((Query(Np+2,a,b)>Np) ? '1' : '0');
    a[i] = i+1;
    b[i] = i+1;
  }
  // now know the first 100 bits
  
  a[-1+Np/2] = 0;
  b[-1+Np/2] = 0;
  a[Np-1] = Np/2;
  b[Np-1] = Np/2;
  for(int i = Np; i < N; i++)
  {
    auto f = Np/2;
    b[i%f] = f + ((1+i)%f);
    a[f+(i%f)] = (i+1)%f;
    s.push_back((Query(a.size(),a,b)>=f ? '1' : '0'));
    b[i%f] = ((1+i)%f);
    a[f+(i%f)] = f + ((1+i)%f);
  }
  return s;
  // now know last 50 bits

  // use that information somehow
    // can query xor of arithmetic sequences (up to 50 long)
    // count how many 1's
  
}

• Subtask 1: 22 / 100