QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#181882#6320. Parallel Processing (Hard)hos_lyricAC ✓1ms3924kbC++144.1kb2023-09-17 02:44:292023-09-17 02:44:30

Judging History

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

  • [2023-09-17 02:44:30]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3924kb
  • [2023-09-17 02:44:29]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


const int V = 2000;

vector<vector<int>> solve(int N) {
  vector<vector<int>> ans;
  int head = 1;
  auto add = [&](vector<int> xs) -> void {
    assert(xs.size() == 8);
    for (int &x : xs) {
      x = (~x) ? (head + x) : V;
    }
    ans.push_back(xs);
  };
  if (N <= 2) {
    add({0,1, 2,3, 4,5, 6,7});
  } else if (N <= 4) {
    add({0,1, 2,3, 4,5, 6,7});
    add({1,2, 1,3, 5,6, 5,7});
  } else if (N <= 8) {
    add({0,1, 2,3, 4,5, 6,7});
    add({1,2, 1,3, 5,6, 5,7});
    add({3,4, 3,5, 3,6, 3,7});
  } else {
    switch (N % 10) {
      case 7: case 8: {
        add({0,1, 2,3, 4,5, 6,7});
        add({1,2, 1,3, 5,6, 5,7});
        add({3,4, 3,5, 3,6, 3,7});
        head += 7;
      } break;
      case 9: case 0: case 1: {
        //
      } break;
      case 2: case 3: {
        add({0,1, 3,4, 6,7,  9,10});
        add({1,2, 4,5, 7,8, 10,11});
        add({2,3, 2,4, 2,5, 11,12});
        add({5,6, 5,7, 5,8, -1,-1});
        add({8,9, 8,10, 8,11, 8,12});
        head += 12;
      } break;
      case 4: case 5: case 6: {
        add({0,1, 4,5,  8, 9, 12,13});
        add({1,2, 5,6,  9,10, 13,14});
        add({2,3, 6,7, 10,11, 14,15});
        add({ 3, 4,  3, 5,  3, 6,  3, 7});
        add({ 7, 8,  7, 9,  7,10,  7,11});
        add({11,12, 11,13, 11,14, 11,15});
        head += 15;
      } break;
      default: assert(false);
    }
    for (; head < N; ) {
      add({0,1,                 2,3, 4,5, 7, 8});
      add({1,2, 1,3,                 5,6, 8, 9});
      add({3,4, 3,5, 3,6,                 9,10});
      add({6,7, 6,8, 6,9, 6,10,               });
      head += 10;
    }
  }
  return ans;
}

void judge(int N, const vector<vector<int>> &ans) {
  vector<vector<int>> mem(V + 1);
  for (int u = 1; u <= V; ++u) {
    mem[u] = {u};
  }
  for (const auto &step : ans) {
    vector<int> tmp[4];
    for (int i = 0; i < 4; ++i) {
      const int u = step[i << 1 | 0];
      const int v = step[i << 1 | 1];
      tmp[i].insert(tmp[i].end(), mem[u].begin(), mem[u].end());
      tmp[i].insert(tmp[i].end(), mem[v].begin(), mem[v].end());
    }
    for (int i = 0; i < 4; ++i) {
      const int v = step[i << 1 | 1];
      mem[v] = tmp[i];
    }
  }
  for (int u = 1; u <= N; ++u) {
    assert((int)mem[u].size() == u);
    for (int i = 1; i <= u; ++i) {
      assert(mem[u][i - 1] == i);
    }
  }
}

int main() {
#ifdef LOCAL
  for (int N = 1; N <= 30; ++N) {
    const auto ans = solve(N);
    cerr << N << ": " << ans.size() << endl;
    judge(N, ans);
  }
#endif
  
  int N;
  for (; ~scanf("%d", &N); ) {
    const auto ans = solve(N);
    printf("%d\n", (int)ans.size());
    for (const auto &step : ans) {
      for (int i = 0; i < 4; ++i) {
        const int u = step[i << 1 | 0];
        const int v = step[i << 1 | 1];
        printf("%d %d %d\n", v, u, v);
      }
    }
#ifdef LOCAL
judge(N,ans);
#endif
  }
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3812kb

input:

17

output:

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

result:

ok AC

Test #2:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

18

output:

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

result:

ok AC

Test #3:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

19

output:

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

result:

ok AC

Test #4:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

20

output:

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

result:

ok AC

Test #5:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

21

output:

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

result:

ok AC

Test #6:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

120

output:

48
2 1 2
4 3 4
6 5 6
9 8 9
3 2 3
4 2 4
7 6 7
10 9 10
5 4 5
6 4 6
7 4 7
11 10 11
8 7 8
9 7 9
10 7 10
11 7 11
12 11 12
14 13 14
16 15 16
19 18 19
13 12 13
14 12 14
17 16 17
20 19 20
15 14 15
16 14 16
17 14 17
21 20 21
18 17 18
19 17 19
20 17 20
21 17 21
22 21 22
24 23 24
26 25 26
29 28 29
23 22 23
24 ...

result:

ok AC

Test #7:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

421

output:

168
2 1 2
4 3 4
6 5 6
9 8 9
3 2 3
4 2 4
7 6 7
10 9 10
5 4 5
6 4 6
7 4 7
11 10 11
8 7 8
9 7 9
10 7 10
11 7 11
12 11 12
14 13 14
16 15 16
19 18 19
13 12 13
14 12 14
17 16 17
20 19 20
15 14 15
16 14 16
17 14 17
21 20 21
18 17 18
19 17 19
20 17 20
21 17 21
22 21 22
24 23 24
26 25 26
29 28 29
23 22 23
24...

result:

ok AC

Test #8:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

464

output:

186
2 1 2
6 5 6
10 9 10
14 13 14
3 2 3
7 6 7
11 10 11
15 14 15
4 3 4
8 7 8
12 11 12
16 15 16
5 4 5
6 4 6
7 4 7
8 4 8
9 8 9
10 8 10
11 8 11
12 8 12
13 12 13
14 12 14
15 12 15
16 12 16
17 16 17
19 18 19
21 20 21
24 23 24
18 17 18
19 17 19
22 21 22
25 24 25
20 19 20
21 19 21
22 19 22
26 25 26
23 22 23
...

result:

ok AC

Test #9:

score: 0
Accepted
time: 1ms
memory: 3816kb

input:

812

output:

325
2 1 2
5 4 5
8 7 8
11 10 11
3 2 3
6 5 6
9 8 9
12 11 12
4 3 4
5 3 5
6 3 6
13 12 13
7 6 7
8 6 8
9 6 9
2000 2000 2000
10 9 10
11 9 11
12 9 12
13 9 13
14 13 14
16 15 16
18 17 18
21 20 21
15 14 15
16 14 16
19 18 19
22 21 22
17 16 17
18 16 18
19 16 19
23 22 23
20 19 20
21 19 21
22 19 22
23 19 23
24 23 ...

result:

ok AC

Test #10:

score: 0
Accepted
time: 1ms
memory: 3860kb

input:

862

output:

345
2 1 2
5 4 5
8 7 8
11 10 11
3 2 3
6 5 6
9 8 9
12 11 12
4 3 4
5 3 5
6 3 6
13 12 13
7 6 7
8 6 8
9 6 9
2000 2000 2000
10 9 10
11 9 11
12 9 12
13 9 13
14 13 14
16 15 16
18 17 18
21 20 21
15 14 15
16 14 16
19 18 19
22 21 22
17 16 17
18 16 18
19 16 19
23 22 23
20 19 20
21 19 21
22 19 22
23 19 23
24 23 ...

result:

ok AC

Test #11:

score: 0
Accepted
time: 1ms
memory: 3924kb

input:

996

output:

398
2 1 2
6 5 6
10 9 10
14 13 14
3 2 3
7 6 7
11 10 11
15 14 15
4 3 4
8 7 8
12 11 12
16 15 16
5 4 5
6 4 6
7 4 7
8 4 8
9 8 9
10 8 10
11 8 11
12 8 12
13 12 13
14 12 14
15 12 15
16 12 16
17 16 17
19 18 19
21 20 21
24 23 24
18 17 18
19 17 19
22 21 22
25 24 25
20 19 20
21 19 21
22 19 22
26 25 26
23 22 23
...

result:

ok AC

Test #12:

score: 0
Accepted
time: 1ms
memory: 3880kb

input:

997

output:

399
2 1 2
4 3 4
6 5 6
8 7 8
3 2 3
4 2 4
7 6 7
8 6 8
5 4 5
6 4 6
7 4 7
8 4 8
9 8 9
11 10 11
13 12 13
16 15 16
10 9 10
11 9 11
14 13 14
17 16 17
12 11 12
13 11 13
14 11 14
18 17 18
15 14 15
16 14 16
17 14 17
18 14 18
19 18 19
21 20 21
23 22 23
26 25 26
20 19 20
21 19 21
24 23 24
27 26 27
22 21 22
23 2...

result:

ok AC

Test #13:

score: 0
Accepted
time: 1ms
memory: 3828kb

input:

998

output:

399
2 1 2
4 3 4
6 5 6
8 7 8
3 2 3
4 2 4
7 6 7
8 6 8
5 4 5
6 4 6
7 4 7
8 4 8
9 8 9
11 10 11
13 12 13
16 15 16
10 9 10
11 9 11
14 13 14
17 16 17
12 11 12
13 11 13
14 11 14
18 17 18
15 14 15
16 14 16
17 14 17
18 14 18
19 18 19
21 20 21
23 22 23
26 25 26
20 19 20
21 19 21
24 23 24
27 26 27
22 21 22
23 2...

result:

ok AC

Test #14:

score: 0
Accepted
time: 1ms
memory: 3816kb

input:

999

output:

400
2 1 2
4 3 4
6 5 6
9 8 9
3 2 3
4 2 4
7 6 7
10 9 10
5 4 5
6 4 6
7 4 7
11 10 11
8 7 8
9 7 9
10 7 10
11 7 11
12 11 12
14 13 14
16 15 16
19 18 19
13 12 13
14 12 14
17 16 17
20 19 20
15 14 15
16 14 16
17 14 17
21 20 21
18 17 18
19 17 19
20 17 20
21 17 21
22 21 22
24 23 24
26 25 26
29 28 29
23 22 23
24...

result:

ok AC

Test #15:

score: 0
Accepted
time: 1ms
memory: 3820kb

input:

1000

output:

400
2 1 2
4 3 4
6 5 6
9 8 9
3 2 3
4 2 4
7 6 7
10 9 10
5 4 5
6 4 6
7 4 7
11 10 11
8 7 8
9 7 9
10 7 10
11 7 11
12 11 12
14 13 14
16 15 16
19 18 19
13 12 13
14 12 14
17 16 17
20 19 20
15 14 15
16 14 16
17 14 17
21 20 21
18 17 18
19 17 19
20 17 20
21 17 21
22 21 22
24 23 24
26 25 26
29 28 29
23 22 23
24...

result:

ok AC