QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#181881#6319. Parallel Processing (Easy)hos_lyricAC ✓0ms4108kbC++144.1kb2023-09-17 02:44:162023-09-17 02:44:16

Judging History

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

  • [2023-09-17 02:44:16]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:4108kb
  • [2023-09-17 02:44:16]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2

output:

1
2 1 2
4 3 4
6 5 6
8 7 8

result:

ok AC

Test #2:

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

input:

4

output:

2
2 1 2
4 3 4
6 5 6
8 7 8
3 2 3
4 2 4
7 6 7
8 6 8

result:

ok AC

Test #3:

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

input:

3

output:

2
2 1 2
4 3 4
6 5 6
8 7 8
3 2 3
4 2 4
7 6 7
8 6 8

result:

ok AC

Test #4:

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

input:

5

output:

3
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

result:

ok AC

Test #5:

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

input:

6

output:

3
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

result:

ok AC

Test #6:

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

input:

7

output:

3
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

result:

ok AC

Test #7:

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

input:

8

output:

3
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

result:

ok AC

Test #8:

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

input:

9

output:

4
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

result:

ok AC

Test #9:

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

input:

10

output:

4
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

result:

ok AC

Test #10:

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

input:

11

output:

4
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

result:

ok AC

Test #11:

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

input:

12

output:

5
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

result:

ok AC

Test #12:

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

input:

13

output:

5
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

result:

ok AC

Test #13:

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

input:

14

output:

6
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

result:

ok AC

Test #14:

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

input:

15

output:

6
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

result:

ok AC

Test #15:

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

input:

16

output:

6
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

result:

ok AC