QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398269#5434. Binary SubstringscaijianhongWA 2ms16548kbC++201.8kb2024-04-25 10:07:172024-04-25 10:07:18

Judging History

你现在查看的是最新测评结果

  • [2024-04-25 10:07:18]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:16548kb
  • [2024-04-25 10:07:17]
  • 提交

answer


#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
typedef long long LL;
int n, k, to[1000010], repr[1000010], bel[1000010];
vector<int> g[1000010];
vector<int> ans;
void dfs(int u) {
  while (!g[u].empty()) {
    int v = g[u].back();
    g[u].pop_back();
    dfs(v);
    ans.push_back(v & 1);
  }
}
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);  
#endif
  cin >> n;
  if (n == 1) return cout << "1" << endl, 0;
  if (n == 2) return cout << "10" << endl, 0;
  while (k + (1 << (k + 1)) <= n) ++k;
  int pk1 = 1 << (k - 1), pk2 = pk1 << 2, pk = pk2 >> 1;
  for (int i = 0; i < pk1; i++) {
    g[i] = {(i << 1 | 1) % pk1, (i << 1) % pk1};
  }
  dfs(0);
  reverse(ans.begin(), ans.end());
  ans.insert(ans.begin(), k - 1, 0);
  memset(to, -1, sizeof to);
  int lst = 0;
  for (int i = 0, now = 0; i < ans.size(); i++) {
    now = (now << 1 | ans[i]) % pk2;
    if (i >= k) to[lst] = now;
    lst = now;
  }
  to[lst] = (lst << 1) % pk2;
  for (int i = 0; i < pk; i++) {
    if (~to[i] && to[i + pk] == -1) to[i + pk] = to[i] ^ 1;
    if (~to[i + pk] && to[i] == -1) to[i] = to[i + pk] ^ 1;
  }
  memset(repr, -1, sizeof repr);
  memset(bel, -1, sizeof bel);
  for (int i = 0; i < pk2; i++) {
    if (~repr[i]) continue;
    bel[i] = i;
    for (int j = i; repr[j] == -1; j = to[j]) repr[j] = i;
  }
  for (int i = 0; i < pk; i++) {
    if (bel[repr[i]] != bel[repr[i + pk]]) {
      int u = repr[i], v = repr[i + pk];
      if (bel[v] == 0) swap(u, v);
      bel[v] = u;
      swap(to[i], to[i + pk]);
    }
  }
  ans.assign(k - 1, 0);
  for (int now = 0; ans.size() < n; now = to[now]) ans.push_back(now & 1);
  for (int x : ans) cout << x;
  cout << endl;
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3716kb

input:

2

output:

10

result:

ok meet maximum 3

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 16548kb

input:

5

output:

00101

result:

wrong answer not meet maximum 11 < 12