QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#450518#1289. A + B Problemyzy1AC ✓101ms8656kbC++232.8kb2024-06-22 14:50:112024-06-22 14:50:11

Judging History

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

  • [2024-06-22 14:50:11]
  • 评测
  • 测评结果:AC
  • 用时:101ms
  • 内存:8656kb
  • [2024-06-22 14:50:11]
  • 提交

answer

#if defined(LOCAL)
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif

#include <bits/stdc++.h>

#if defined(LOCAL)
#define DBG_MACRO_NO_WARNING
#include <dbg.hpp>
#else
#define dbg(x...) (0)
#endif

using namespace std;

using ll = long long;

// #define int ll
#define rep(i, f, t) for (int i = (f), ed##i = (t); i <= ed##i; ++i)
#define re(i, t) rep (i, 1, t)
#define per(i, t, f) for (int i = (t), ed##i = (f); i >= ed##i; --i)
#define ste(i, f, t, s) for (int i = (f), ed##i = (t); i <= ed##i; i += s)
#define nxt(i, f, g) for (int i = g.h[f]; i; i = g.e[i].n)
#define umod(x) ((x) >= mo && ((x) -= mo))
#define dmod(x) ((x) < 0 && ((x) += mo))
#define y1 y1__
#define fio(x) (freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout))

template <class T, class E>
__attribute__((always_inline)) inline void up(T &x, E &&y) {
  if (x < y) x = y;
}
template <class T, class E>
__attribute__((always_inline)) inline void down(T &x, E &&y) {
  if (y < x) x = y;
}

const int N = 2e6 + 9;
int n, m, a[N], ans1[N], ans2[N];
vector<int> one;

inline bool Ck(int len1, int len2, int p) {
  int dif = len2 - (len1 - 1);
  int onecnt = one.end() - upper_bound(one.begin(), one.end(), p);
  if (onecnt < dif) return 0;
  int np = *(lower_bound(one.begin(), one.end(), p) + dif);
  int zerocnt = np - p - dif;
  if (zerocnt > len1 - 1) return 0;
  return 1;
}

inline void Work() {
  cin >> n >> m;
  if (n < m) swap(n, m);
  one.clear();
  re (i, n + m) {
    char c;
    cin >> c;
    a[i] = c - '0';
    if (a[i] == 1) one.push_back(i);
  }
  rep (i, 0, n + m + 1) ans1[i] = ans2[i] = 0;
  int hd1 = 0, hd2 = n - m;
  re (i, n + m) {
    if (a[i] == 0) {
      if (hd1 == n)
        ans2[++hd2] = 0;
      else if (hd2 == n)
        ans1[++hd1] = 0;
      else if (hd1 > hd2)
        ans1[++hd1] = 0;
      else
        ans2[++hd2] = 0;
      continue;
    }
    if (hd1 == n)
      ans2[++hd2] = 1;
    else if (hd2 == n)
      ans1[++hd1] = 1;
    else if (hd1 >= hd2) {
      if (Ck(n - hd1, n - hd2, i))
        ans1[++hd1] = 1;
      else
        ans2[++hd2] = 1;
    } else {
      if (Ck(n - hd2, n - hd1, i))
        ans2[++hd2] = 1;
      else
        ans1[++hd1] = 1;
    }
  }
  assert(hd1 == n);
  assert(hd2 == n);
  // dbg(hd1, hd2);
  // re (i, n) cerr << ans1[i];
  // cerr << '\n';
  // re (i, n) cerr << ans2[i];
  // cerr << '\n';
  per (i, n, 1) {
    ans1[i] += ans2[i], ans1[i - 1] += ans1[i] >> 1, ans1[i] &= 1;
  }
  rep (i, 0, n) {
    if (ans1[i]) {
      rep (j, i, n) cout << ans1[j];
      cout << '\n';
      return;
    }
  }
  cout << "0\n";
}

signed main() {
  // fio("partition");
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T;
  cin >> T;
  while (T--) Work();
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7736kb

input:

3
4 3
1000101
2 2
1111
1 1
00

output:

1101
110
0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 101ms
memory: 8656kb

input:

11110
10 8
111011010011100100
3 5
01011000
7 6
1110101010000
9 1
0110100101
1 9
0100001110
8 10
000101101011111000
9 6
011111111000111
1 9
1011101101
10 7
00100011000100000
4 9
1000101101010
8 4
100100110000
8 9
00101111011000101
8 9
11000000101011110
7 6
1111010100110
2 9
01001110101
4 5
100010100
...

output:

10011010100
11100
10101000
110100101
100001110
10000001100
1000010111
111101101
1110100000
111101010
11110000
1000011101
1001011110
10101110
101110101
11100
1111010
1000010
1011100010
10010101001
10010001
1001010
1000000010
1110
111
1111110001
10110111
1100010101
10000000
111000011
110
11111
1100101...

result:

ok 11110 lines