QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#181881 | #6319. Parallel Processing (Easy) | hos_lyric | AC ✓ | 0ms | 4108kb | C++14 | 4.1kb | 2023-09-17 02:44:16 | 2023-09-17 02:44:16 |
Judging History
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: 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