Submission #830185

#	Time	Username	Problem	Language	Result	Execution time	Memory
830185		ikaurov	Ancient Machine 2 (JOI23_ancient2)	C++17	97 / 100	41 ms	696 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;

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 = N - 1; i >= 0; 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) == N) return;
    }
  }
}

std::string Solve(int n) {
  precalc();
  for (int i = 0; i < N; 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);
  }
  string ans;
  for (int i = 0; i < n; i++){
    for (int j = 0; j < N; j++){
      if (basisy[i].test(j)) val[i] ^= res[j];
      if (j < i && basisx[i].test(j)) val[i] ^= val[j];
    }
    ans.pb('0' + val[i]);
  }
  return ans;
}

• Subtask 1: 97 / 100