QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#426644#6320. Parallel Processing (Hard)yzy1AC ✓1ms3932kbC++237.3kb2024-05-31 16:46:352024-05-31 16:46:36

Judging History

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

  • [2024-05-31 16:46:36]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3932kb
  • [2024-05-31 16:46:35]
  • 提交

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 == 11) {
    Ans.push_back({l + 1, l, l + 1, l + 3, l + 2, l + 3, l + 5, l + 4, l + 5, l + 8, l + 7, l + 8});
    Ans.push_back(
        {l + 2, l + 1, l + 2, l + 3, l + 1, l + 3, l + 6, l + 5, l + 6, l + 9, l + 8, l + 9});
    Ans.push_back(
        {l + 4, l + 3, l + 4, l + 5, l + 3, l + 5, l + 6, l + 3, l + 6, l + 10, l + 9, l + 10});
    Ans.push_back(
        {l + 7, l + 6, l + 7, l + 8, l + 6, l + 8, l + 9, l + 6, l + 9, l + 10, l + 6, l + 10});
    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 <= 15) {
    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 = max(4, 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) {
    if (i + 3 <= n) dq2.push_back({i + 3, i - 1});
    dq2.push_back({i, i - 1});
    if (i + 2 <= n) dq2.push_back({i + 2, i - 1});
    if (i + 1 <= n) dq2.push_back({i + 1, 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()) x2 = dq2.front(), dq2.pop_front();
    if (dq2.size()) x3 = dq2.front(), dq2.pop_front();
    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});
  }
  cout << Ans.size() << '\n';
  for (auto a : Ans) {
    rep (i, 0, 11) cout << (a[i] ?: 2000) << " \n"[i % 3 == 2];
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

17

output:

7
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
8 4 8
5 4 5
7 4 7
6 4 6
12 8 12
9 8 9
11 8 11
10 8 10
16 12 16
13 12 13
15 12 15
14 12 14
17 16 17
2000 2000 2000
2000 2000 2000
2000 2000 2000

result:

ok AC

Test #2:

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

input:

18

output:

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

result:

ok AC

Test #3:

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

input:

19

output:

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

result:

ok AC

Test #4:

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

input:

20

output:

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

result:

ok AC

Test #5:

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

input:

21

output:

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

result:

ok AC

Test #6:

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

input:

120

output:

48
2 1 2
26 25 26
30 29 30
34 33 34
3 2 3
38 37 38
42 41 42
46 45 46
4 3 4
50 49 50
54 53 54
58 57 58
5 4 5
62 61 62
66 65 66
70 69 70
6 5 6
74 73 74
78 77 78
82 81 82
7 6 7
86 85 86
90 89 90
94 93 94
8 7 8
98 97 98
102 101 102
106 105 106
9 8 9
110 109 110
114 113 114
118 117 118
10 9 10
27 26 27
3...

result:

ok AC

Test #7:

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

input:

421

output:

168
2 1 2
86 85 86
90 89 90
94 93 94
3 2 3
98 97 98
102 101 102
106 105 106
4 3 4
110 109 110
114 113 114
118 117 118
5 4 5
122 121 122
126 125 126
130 129 130
6 5 6
134 133 134
138 137 138
142 141 142
7 6 7
146 145 146
150 149 150
154 153 154
8 7 8
158 157 158
162 161 162
166 165 166
9 8 9
170 169 ...

result:

ok AC

Test #8:

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

input:

464

output:

186
2 1 2
94 93 94
98 97 98
102 101 102
3 2 3
106 105 106
110 109 110
114 113 114
4 3 4
118 117 118
122 121 122
126 125 126
5 4 5
130 129 130
134 133 134
138 137 138
6 5 6
142 141 142
146 145 146
150 149 150
7 6 7
154 153 154
158 157 158
162 161 162
8 7 8
166 165 166
170 169 170
174 173 174
9 8 9
17...

result:

ok AC

Test #9:

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

input:

812

output:

325
2 1 2
164 163 164
168 167 168
172 171 172
3 2 3
176 175 176
180 179 180
184 183 184
4 3 4
188 187 188
192 191 192
196 195 196
5 4 5
200 199 200
204 203 204
208 207 208
6 5 6
212 211 212
216 215 216
220 219 220
7 6 7
224 223 224
228 227 228
232 231 232
8 7 8
236 235 236
240 239 240
244 243 244
9 ...

result:

ok AC

Test #10:

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

input:

862

output:

345
2 1 2
174 173 174
178 177 178
182 181 182
3 2 3
186 185 186
190 189 190
194 193 194
4 3 4
198 197 198
202 201 202
206 205 206
5 4 5
210 209 210
214 213 214
218 217 218
6 5 6
222 221 222
226 225 226
230 229 230
7 6 7
234 233 234
238 237 238
242 241 242
8 7 8
246 245 246
250 249 250
254 253 254
9 ...

result:

ok AC

Test #11:

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

input:

996

output:

398
2 1 2
201 200 201
205 204 205
209 208 209
3 2 3
213 212 213
217 216 217
221 220 221
4 3 4
225 224 225
229 228 229
233 232 233
5 4 5
237 236 237
241 240 241
245 244 245
6 5 6
249 248 249
253 252 253
257 256 257
7 6 7
261 260 261
265 264 265
269 268 269
8 7 8
273 272 273
277 276 277
281 280 281
9 ...

result:

ok AC

Test #12:

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

input:

997

output:

399
2 1 2
201 200 201
205 204 205
209 208 209
3 2 3
213 212 213
217 216 217
221 220 221
4 3 4
225 224 225
229 228 229
233 232 233
5 4 5
237 236 237
241 240 241
245 244 245
6 5 6
249 248 249
253 252 253
257 256 257
7 6 7
261 260 261
265 264 265
269 268 269
8 7 8
273 272 273
277 276 277
281 280 281
9 ...

result:

ok AC

Test #13:

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

input:

998

output:

399
2 1 2
201 200 201
205 204 205
209 208 209
3 2 3
213 212 213
217 216 217
221 220 221
4 3 4
225 224 225
229 228 229
233 232 233
5 4 5
237 236 237
241 240 241
245 244 245
6 5 6
249 248 249
253 252 253
257 256 257
7 6 7
261 260 261
265 264 265
269 268 269
8 7 8
273 272 273
277 276 277
281 280 281
9 ...

result:

ok AC

Test #14:

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

input:

999

output:

400
2 1 2
201 200 201
205 204 205
209 208 209
3 2 3
213 212 213
217 216 217
221 220 221
4 3 4
225 224 225
229 228 229
233 232 233
5 4 5
237 236 237
241 240 241
245 244 245
6 5 6
249 248 249
253 252 253
257 256 257
7 6 7
261 260 261
265 264 265
269 268 269
8 7 8
273 272 273
277 276 277
281 280 281
9 ...

result:

ok AC

Test #15:

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

input:

1000

output:

400
2 1 2
202 201 202
206 205 206
210 209 210
3 2 3
214 213 214
218 217 218
222 221 222
4 3 4
226 225 226
230 229 230
234 233 234
5 4 5
238 237 238
242 241 242
246 245 246
6 5 6
250 249 250
254 253 254
258 257 258
7 6 7
262 261 262
266 265 266
270 269 270
8 7 8
274 273 274
278 277 278
282 281 282
9 ...

result:

ok AC