Submission #830180

#	Time	Username	Problem	Language	Result	Execution time	Memory
830180		ikaurov	Ancient Machine 2 (JOI23_ancient2)	C++17	37 / 100	68 ms	516 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'

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) {
  int half1 = n / 2, half2 = n - half1;
  string s, t;
  for (int i = 0; i < half1; 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;
    s.pb(Query(sz(a), a, b) == i + 1? '0' : '1');
  }
  for (int i = 0; i < half2; i++){
    auto aut = build_automaton("0" + t);
    t = (Query(sz(aut[0]), aut[0], aut[1]) == sz(t) + 1? "0" : "1") + t;
  }
  return s + t;
}

• Subtask 1: 37 / 100