QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#426594	#6320. Parallel Processing (Hard)	yzy1	WA	1ms	3796kb	C++23	6.9kb	2024-05-31 15:57:09	2024-05-31 15:57:10

Judging History

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

[2024-05-31 15:57:10]
评测

测评结果：WA
用时：1ms
内存：3796kb

查看

[2024-05-31 15:57:09]
提交

answer

#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 each(i, x) for (auto &&i : (x))
#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;
}

int n;

vector<array<int, 12>> Ans;

inline void Work(int l, int r) {
  if (l == r) return;
  if (r - l + 1 == 2) {
    Ans.push_back({r, l, r});
    return;
  }
  if (r - l + 1 == 3) {
    Ans.push_back({l + 1, l, l + 1});
    Ans.push_back({l + 2, l + 1, l + 2});
    return;
  }
  if (r - l + 1 == 4) {
    Ans.push_back({l + 1, l, l + 1, l + 2, l + 1, l + 2, l + 3, l + 2, l + 3});
    Ans.push_back({l + 2, l, l + 2, l + 3, l + 1, l + 3});
    return;
  }
  if (r - l + 1 == 5) {
    Ans.push_back({l + 1, l, l + 1, l + 2, l + 1, l + 2, l + 3, l + 2, l + 3, l + 4, l + 3, l + 4});
    Ans.push_back({l + 2, l, l + 2, l + 3, l + 1, l + 3});
    Ans.push_back({l + 4, l + 2, l + 4});
    return;
  }
  if (r - l + 1 == 6) {
    Ans.push_back({l + 1, l, l + 1, l + 2, l + 1, l + 2, l + 3, l + 2, l + 3, l + 4, l + 3, l + 4});
    Ans.push_back({l + 2, l, l + 2, l + 3, l + 1, l + 3, l + 5, l + 4, l + 5});
    Ans.push_back({l + 4, l + 2, l + 4, l + 5, l + 2, l + 5});
    return;
  }
  if (r - l + 1 == 7) {
    Ans.push_back({l + 1, l, l + 1, l + 2, l + 1, l + 2, l + 3, l + 2, l + 3, l + 5, l + 4, l + 5});
    Ans.push_back({l + 2, l, l + 2, l + 3, l + 1, l + 3, l + 6, l + 5, l + 6});
    Ans.push_back({l + 4, l + 3, l + 4, l + 5, l + 3, l + 5, l + 6, l + 3, l + 6});
    return;
  }
  if (r - l + 1 == 8) {
    Ans.push_back({l + 1, l, l + 1, l + 3, l + 2, l + 3, l + 5, l + 4, l + 5, l + 7, l + 6, l + 7});
    Ans.push_back(
        {l + 2, l + 1, l + 2, l + 3, l + 1, l + 3, l + 6, l + 5, l + 6, l + 7, l + 5, l + 7});
    Ans.push_back(
        {l + 4, l + 3, l + 4, l + 5, l + 3, l + 5, l + 6, l + 3, l + 6, l + 7, l + 3, l + 7});
    return;
  }
  if (r - l + 1 == 10) {
    Ans.push_back({l + 1, l, l + 1, l + 3, l + 2, l + 3, l + 5, l + 4, l + 5, l + 7, l + 6, l + 7});
    Ans.push_back(
        {l + 2, l + 1, l + 2, l + 3, l + 1, l + 3, l + 6, l + 5, l + 6, l + 7, l + 5, l + 7});
    Ans.push_back(
        {l + 4, l + 3, l + 4, l + 7, l + 3, l + 7, l + 8, l + 7, l + 8, l + 9, l + 8, l + 9});
    Ans.push_back(
        {l + 5, l + 3, l + 5, l + 6, l + 3, l + 6, l + 8, l + 3, l + 8, l + 9, l + 7, l + 9});
    return;
  }
  if (r - l + 1 == 12) {
    Ans.push_back({l + 1, l, l + 1, l + 3, l + 2, l + 3, l + 5, l + 4, l + 5, l + 7, l + 6, l + 7});
    Ans.push_back(
        {l + 2, l + 1, l + 2, l + 3, l + 1, l + 3, l + 6, l + 5, l + 6, l + 7, l + 5, l + 7});
    Ans.push_back(
        {l + 4, l + 3, l + 4, l + 7, l + 3, l + 7, l + 8, l + 7, l + 8, l + 9, l + 8, l + 9});
    Ans.push_back(
        {l + 5, l + 3, l + 5, l + 6, l + 3, l + 6, l + 9, l + 7, l + 9, l + 11, l + 10, l + 11});
    Ans.push_back({l + 8, l + 3, l + 8, l + 10, l + 9, l + 10, l + 11, l + 9, l + 11});
    return;
  }
  if (r - l + 1 == 13) {
    Ans.push_back({l + 1, l, l + 1, l + 3, l + 2, l + 3, l + 5, l + 4, l + 5, l + 7, l + 6, l + 7});
    Ans.push_back(
        {l + 2, l + 1, l + 2, l + 3, l + 1, l + 3, l + 6, l + 5, l + 6, l + 7, l + 5, l + 7});
    Ans.push_back(
        {l + 4, l + 3, l + 4, l + 7, l + 3, l + 7, l + 9, l + 8, l + 9, l + 11, l + 10, l + 11});
    Ans.push_back(
        {l + 5, l + 3, l + 5, l + 6, l + 3, l + 6, l + 9, l + 7, l + 9, l + 12, l + 11, l + 12});
    Ans.push_back(
        {l + 8, l + 7, l + 8, l + 10, l + 9, l + 10, l + 11, l + 9, l + 11, l + 12, l + 9, l + 12});
    return;
  }
  Work(l, l + 7);
  Work(l + 7, r);
}

deque<pair<int, int>> dq1, dq2;

signed main() {
  // #ifndef LOCAL
  //   fio("cpu");
  // #endif
  //   ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  //   int Test;
  //   cin >> Test;
  cin >> n;
  if (n <= 16) {
    Work(1, n);
    cout << Ans.size() << '\n';
    for (auto a : Ans) {
      rep (i, 0, 11) cout << (a[i] ?: 2000) << " \n"[i % 3 == 2];
    }
    exit(0);
  }
  int sz = n / 5;
  dbg(sz);
  for (int j : {2, 3, 0})
    rep (i, sz + 1, n)
      if ((i - sz) % 4 == j) dq1.push_back({i, i - 1});
  rep (i, 2, sz) {
    pair<int, int> x1 = {2000, 2000}, x2 = {2000, 2000}, x3 = {2000, 2000};
    if (dq1.size()) x1 = dq1.front(), dq1.pop_front();
    if (dq1.size()) x2 = dq1.front(), dq1.pop_front();
    if (dq1.size()) x3 = dq1.front(), dq1.pop_front();
    Ans.push_back({i, i - 1, i, x1.first, x1.second, x1.first, x2.first, x2.second, x2.first,
                   x3.first, x3.second, x3.first});
  }
  ste (i, sz + 1, n, 4) {
    dq2.push_back({i, i - 1});
    if (i + 1 <= n) dq2.push_back({i + 1, i - 1});
    if (i + 2 <= n) dq2.push_back({i + 2, i - 1});
    if (i + 3 <= n) dq2.push_back({i + 3, i - 1});
  }
  while (dq1.size()) {
    assert(dq2.size());
    pair<int, int> x1 = dq2.front(), x2 = {2000, 2000}, x3 = {2000, 2000}, x4 = {2000, 2000};
    dq2.pop_front();
    if (dq1.size())
      x2 = dq1.front(), dq1.pop_front();
    else if (dq2.size())
      x2 = dq2.front(), dq2.pop_front();
    if (dq1.size())
      x3 = dq1.front(), dq1.pop_front();
    else if (dq2.size())
      x3 = dq2.front(), dq2.pop_front();
    if (dq1.size())
      x4 = dq1.front(), dq1.pop_front();
    else if (dq2.size())
      x4 = dq2.front(), dq2.pop_front();
    Ans.push_back({x1.first, x1.second, x1.first, x2.first, x2.second, x2.first, x3.first,
                   x3.second, x3.first, x4.first, x4.second, x4.first});
  }
  while (dq2.size()) {
    pair<int, int> x1 = dq2.front(), x2 = {2000, 2000}, x3 = {2000, 2000}, x4 = {2000, 2000};
    dq2.pop_front();
    if (dq2.size() && dq2.front().second == x1.second) x2 = dq2.front(), dq2.pop_front();
    if (dq2.size() && dq2.front().second == x1.second) x3 = dq2.front(), dq2.pop_front();
    if (dq2.size() && dq2.front().second == x1.second) x4 = dq2.front(), dq2.pop_front();
    Ans.push_back({x1.first, x1.second, x1.first, x2.first, x2.second, x2.first, x3.first,
                   x3.second, x3.first, x4.first, x4.second, x4.first});
  }
  cout << Ans.size() << '\n';
  for (auto a : Ans) {
    rep (i, 0, 11) cout << (a[i] ?: 2000) << " \n"[i % 3 == 2];
  }
  return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3796kb

input:

output:

7
2 1 2
5 4 5
9 8 9
13 12 13
3 2 3
17 16 17
6 5 6
10 9 10
4 3 4
14 13 14
7 6 7
11 10 11
5 3 5
15 14 15
6 3 6
7 3 7
8 7 8
9 7 9
10 7 10
11 7 11
12 11 12
13 11 13
14 11 14
15 11 15
16 15 16
17 15 17
2000 2000 2000
2000 2000 2000

result:

ok AC

Test #2:

score: -100

Wrong Answer

time: 0ms

memory: 3636kb

input:

output:

8
2 1 2
5 4 5
9 8 9
13 12 13
3 2 3
17 16 17
6 5 6
10 9 10
4 3 4
14 13 14
18 17 18
7 6 7
5 3 5
11 10 11
15 14 15
6 3 6
7 3 7
2000 2000 2000
2000 2000 2000
2000 2000 2000
8 7 8
9 7 9
10 7 10
11 7 11
12 11 12
13 11 13
14 11 14
15 11 15
16 15 16
17 15 17
18 15 18
2000 2000 2000

result:

wrong answer L = 8 is larger than 7