QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#181882 | #6320. Parallel Processing (Hard) | hos_lyric | AC ✓ | 1ms | 3924kb | C++14 | 4.1kb | 2023-09-17 02:44:29 | 2023-09-17 02:44:30 |
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;
}
Details
Tip: Click on the bar to expand more detailed information
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