Submission #990196

#	Time	Username	Problem	Language	Result	Execution time	Memory
990196		canadavid1	Ancient Machine 2 (JOI23_ancient2)	C++17	37 / 100	82 ms	596 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 = 500;
  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;
  }
  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 < Np + (Np/2); i++)
  {
    auto f = Np/2;
    // query xor of bits in residue class
    b[i%f] = f+(1+i)%f;
    b[f+(i%f)] = (1+i)%f;
    s.push_back((Query(a.size(),a,b)>=f ? '1' : '0'));
    b[i%f] = (1+i)%f;
    b[f+(i%f)] = f+(1+i)%f;
  }
  
  
  for(int i = Np+(Np/2); 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);
  }
  for(int i = 0; i < 250; i++)
  {
    s[500+i] = ((s[i]=='1') ^ (s[250+i]=='1') ^ (s[500+i]=='1') ^ (s[750+i]=='1')) ? '1' : '0';
  }

  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: 37 / 100