Submission #830200

#	Time	Username	Problem	Language	Result	Execution time	Memory
830200		ikaurov	Ancient Machine 2 (JOI23_ancient2)	C++17	100 / 100	35 ms	656 KiB

ancient2

#include "ancient2.h"
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define endl '\n'

const int N = 1000, LB = 100, UB = 898;

bitset<N> basisx[N], basisy[N];
bool res[N], val[N];
vector<pair<int, int>> pairs;

void try_add(int q, int p){
  bitset<N> curx, cury;
  for (int i = q; i < N; i += p) curx.set(i);
  for (int i = UB; i >= LB; i--){
    if (!curx.test(i)) continue;
    if (!basisx[i].any()){
      cury.set(sz(pairs));
      pairs.pb({q, p});
      basisx[i] = curx, basisy[i] = cury;
      return;
    }
    curx ^= basisx[i], cury ^= basisy[i];
  }
}

void precalc(){
  for (int p = 1;; p++){
    for (int q = 0; q < p; q++){
      try_add(q, p);
      if (sz(pairs) == UB - LB + 1) return;
    }
  }
}

vector<int> prefix_function(string s){
  int n = sz(s);
  vector<int> pi(n);
  for (int i = 1; i < n; i++){
    int k = pi[i - 1];
    while (k && s[k] != s[i]) k = pi[k - 1];
    pi[i] = k + (s[i] == s[k]);
  }
  return pi;
}
 
vector<vector<int>> build_automaton(string s){
  auto pi = prefix_function(s);
  int n = sz(s);
  vector<vector<int>> aut(2, vector<int>(n + 1));
  for (int i = 0; i <= n; i++){
    for (int c = 0; c < 2; c++){
      if (s[i] == '0' + c) aut[c][i] = i + 1;
      else if (i) aut[c][i] = aut[c][pi[i - 1]];
    }
  }
  return aut;
}

std::string Solve(int n) {
  precalc();
  for (int i = 0; i < sz(pairs); i++){
    auto [q, p] = pairs[i];
    vector<int> a(2 * p), b(2 * p);
    iota(all(a), 1);
    iota(all(b), 1);
    a[p - 1] = 0, a[2 * p - 1] = p;
    b[p - 1] = 0, b[2 * p - 1] = p;
    b[q] = p + (q + 1) % p, b[p + q] = (q + 1) % p;
    res[i] = (Query(2 * p, a, b) >= p);
  }

  for (int i = 0; i < LB; i++){
    vector<int> a(i + 3), b(i + 3);
    iota(all(a), 1);
    iota(all(b), 1);
    a[i] = i + 1, b[i] = i + 2;
    a[i + 1] = b[i + 1] = i + 1;
    a[i + 2] = b[i + 2] = i + 2;
    val[i] = (Query(sz(a), a, b) == i + 2);
  }

  string t;
  for (int i = n - 1; i > UB; i--){
    auto aut = build_automaton("0" + t);
    t = (Query(sz(aut[0]), aut[0], aut[1]) == sz(t) + 1? "0" : "1") + t;
    val[i] = t[0] - '0';
  }

  for (int i = 0; i < sz(pairs); i++){
    for (int j = 0; j < n; j++){
      if ((j < LB || j > UB) && j % pairs[i].se == pairs[i].fi) res[i] ^= val[j];
    }
  }

  for (int i = LB; i <= UB; i++){
    for (int j = 0; j < sz(pairs); j++){
      if (basisy[i].test(j)) val[i] ^= res[j];
    }
    for (int j = LB; j < i; j++){
      if (basisx[i].test(j)) val[i] ^= val[j];
    }
  }
  string ans;
  for (int i = 0; i < n; i++) ans.pb(val[i] + '0');
  return ans;
}

• Subtask 1: 100 / 100