QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#387807#7757. Palm Islandberarchegas#AC ✓15ms6336kbC++202.3kb2024-04-12 20:47:032024-04-12 20:47:04

Judging History

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

  • [2024-04-12 20:47:04]
  • 评测
  • 测评结果：AC
  • 用时：15ms
  • 内存：6336kb
查看
  • [2024-04-12 20:47:03]
  • 提交

answer

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
    
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 5;
const ll INF = 2e18;

bool inv[1005][1005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n), b(n), na, nb, posa(n + 1), posb(n + 1);
        for (int &x : a) cin >> x;
        for (int &x : b) cin >> x;
        for (int i = 0; i < n; i++) {
            if (a[i] == 1) {
                for (int j = i + 1; j < n; j++) {
                    na.push_back(a[j]);
                }
                for (int j = 0; j < i; j++) {
                    na.push_back(a[j]);;
                }
            }
            if (b[i] == 1) {
                for (int j = i + 1; j < n; j++) {
                    nb.push_back(b[j]);
                }
                for (int j = 0; j < i; j++) {
                    nb.push_back(b[j]);;
                }
            }
        }
        for (int i = 0; i < n - 1; i++) {
            posa[na[i]] = i;
            posb[nb[i]] = i;
        }
        int cnt = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= n; j++) {
                if (posa[i] < posa[j] && posb[i] > posb[j]) inv[i][j] = true;
                if (posa[i] > posa[j] && posb[i] < posb[j]) inv[i][j] = true;
                cnt += inv[i][j];
            }
        }
        string ans;
        deque<int> v(n);
        for (int i = 0; i < n; i++) v[i] = a[i];
        while (cnt) {
            int f = v[0], s = v[1];
            v.pop_front(), v.pop_front();
            if (inv[f][s]) {
                cnt-=2;
                inv[f][s] = inv[s][f] = false;
                ans += '2';
                v.push_front(f);
                v.push_back(s);
            }
            else {
                ans += '1';
                v.push_front(s);
                v.push_back(f);
            }
        }
        while (v[0] != b[0]) {
            ans += '1';
            int f = v[0];
            v.pop_front();
            v.push_back(f);
        }
        cout << ans << '\n';
    }
    return 0;
}
源文件, 语言: C++20

这程序好像有点Bug，我给组数据试试？

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3832kb

input:

2
3
1 2 3
2 3 1
4
1 2 3 4
2 1 3 4

output:

1
122

result:

ok Correct. (2 test cases)

Test #2:

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

input:

200
3
3 1 2
2 3 1
4
2 4 1 3
2 1 4 3
4
1 4 2 3
2 1 3 4
5
4 3 2 1 5
2 4 5 3 1
5
2 1 5 4 3
5 2 4 1 3
4
4 3 1 2
1 2 4 3
3
1 2 3
3 1 2
4
1 4 2 3
2 1 4 3
4
1 3 2 4
1 4 3 2
3
3 2 1
1 3 2
3
2 3 1
1 3 2
4
1 4 3 2
3 1 2 4
3
1 2 3
1 3 2
3
3 2 1
2 3 1
5
5 1 3 2 4
2 4 5 1 3
4
4 3 1 2
1 4 3 2
4
1 3 4 2
2 4 3 1
3
...

output:

11
21121
1121121
12112211121111
11122112
11
11
112
11211211
11
21
1121121
121
211
111
111221
122112111
1

21112111
112111
122112
211
11211
222111211121111
1
2111222111
11121112
112111
11112111211121111
11211
21122
12
221111
221112111
121121
211
22111
11121
111
221
11
122211
111221
1112111
1212111211...

result:

ok Correct. (200 test cases)

Test #3:

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

input:

200
5
5 1 3 4 2
5 3 2 4 1
5
5 1 2 4 3
3 5 4 1 2
5
1 4 5 3 2
2 5 4 3 1
5
1 5 4 3 2
4 5 2 3 1
5
2 3 4 5 1
5 4 3 2 1
5
1 5 2 4 3
5 3 1 2 4
5
1 2 4 3 5
4 2 3 5 1
5
3 2 1 4 5
4 2 3 1 5
5
3 1 2 5 4
2 4 1 3 5
5
5 3 1 4 2
2 5 4 1 3
5
5 4 3 1 2
2 5 4 1 3
5
3 4 5 2 1
3 5 1 4 2
5
4 5 1 3 2
4 2 3 1 5
5
1 3 4 5 ...

output:

11122111211121111
11122111
1212111211121111
121211
222112211121111
122
121111
2112
11212111211121
211222112
1211121112
2121112
21122211221111
1222112211121

221112111211
11122
122
1112221121111
112221122111211
2112211
1111221121111
111211121112111
111122111
112121112
111
11112111211121111
1221112
21...

result:

ok Correct. (200 test cases)

Test #4:

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

input:

100
5
1 2 5 4 3
2 4 5 3 1
6
6 1 5 2 4 3
1 4 5 6 2 3
3
2 1 3
1 2 3
5
5 3 4 2 1
1 2 3 5 4
10
5 9 4 2 6 10 7 8 3 1
1 3 4 10 5 7 2 9 8 6
10
5 9 10 7 8 3 4 6 2 1
2 7 4 3 10 9 5 8 1 6
8
1 7 4 6 3 5 2 8
3 5 1 4 6 8 7 2
4
2 3 4 1
1 4 2 3
7
3 7 4 6 2 1 5
5 6 7 3 4 1 2
8
2 1 4 7 8 3 6 5
5 2 7 4 3 1 8 6
4
3 2 ...

output:

112111
1112121121211
1121
21211121112111
1221222211211221211111221211111211211111111211111111211111111211111111211111111
22212222112212222111212222111112222111111222111111122111111122111111111
122112211111221111112111111211
1211211
2122111122111122111112111112
1122122211212221111222111111
11122
2122...

result:

ok Correct. (100 test cases)

Test #5:

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

input:

100
10
6 9 8 10 4 3 7 1 5 2
3 4 1 8 7 2 10 9 6 5
10
8 1 4 7 9 3 10 2 5 6
7 3 6 5 10 2 1 8 4 9
10
10 1 8 2 3 7 5 4 6 9
9 5 6 10 7 1 3 4 8 2
10
9 1 2 5 6 4 3 10 8 7
8 1 10 3 6 5 7 4 9 2
10
4 9 2 8 1 5 3 6 7 10
6 1 7 10 5 8 3 4 9 2
10
6 3 2 9 5 4 8 7 1 10
4 6 10 9 3 2 7 1 8 5
10
8 1 3 9 6 2 4 5 7 10
9 ...

output:

22212211222221211112211211112111211111111211111111211111111211111
111211122211111122211111112211111111211111111211111111211111111211111111211
111212222211211212111111212111111211
11222221221121221221111221211111221111111121111111
1121111222222111221121111221121111111121111
11222211121222211111122211...

result:

ok Correct. (100 test cases)

Test #6:

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

input:

20
6
3 1 4 6 2 5
6 2 5 4 3 1
44
28 15 14 27 17 41 25 23 7 8 26 30 44 32 6 21 35 33 22 24 9 16 5 34 39 42 3 11 40 10 43 31 37 20 38 18 1 4 12 36 19 2 29 13
43 25 20 4 14 22 18 26 42 13 2 31 33 19 41 11 27 40 35 38 23 28 16 44 6 17 5 3 29 37 34 21 36 8 32 24 39 9 12 30 10 1 15 7
14
3 5 12 7 14 1 4 13 ...

output:

11222111
222122221212222222222222222212222221112222222222222222222222222222222221222222111122222222222222121222221122222222122222211111212222222222212122222112221222212222221111111222112222121212222211222122221222222111111122211221212121212221122212222122222211111111221112121211121222112221222212222...

result:

ok Correct. (20 test cases)

Test #7:

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

input:

20
50
4 42 15 50 26 41 35 16 10 49 28 14 23 48 43 45 29 31 36 17 32 5 30 25 2 24 21 20 12 39 11 13 1 27 47 7 46 33 3 44 19 38 34 18 37 6 8 9 40 22
31 45 2 42 32 6 46 20 8 4 40 14 26 28 25 44 27 34 48 15 11 3 38 22 50 33 5 16 47 35 37 18 10 12 9 13 39 17 24 43 21 19 41 29 23 1 7 36 49 30
50
7 5 12 8 ...

output:

211212222221222222222222222222211122222122222222222222222222122212222222222222221112212212212221222222222222212221222222222222222111111121221122122222222212221212122222222222222211111112112112212222222221222121212222222221222221111111111211221222222212122212121221222221122222111111111111122122222221...

result:

ok Correct. (20 test cases)

Test #8:

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

input:

10
71
20 30 27 60 41 33 44 9 64 11 70 42 12 46 37 29 18 13 10 57 5 66 1 38 54 61 2 69 15 68 50 63 21 7 52 4 25 32 59 31 36 56 16 40 28 65 39 53 48 35 55 23 62 17 67 6 22 34 14 49 45 19 71 51 43 58 24 8 3 26 47
67 6 57 64 39 41 26 70 37 4 31 33 50 38 12 14 25 66 71 49 27 10 36 7 28 34 46 52 1 19 22 2...

output:

212222222222122222222112222222221122222222222222222222222222222222222222222222222222222222221122121122112222222221222222222222122222222222222222222222222222222221111212112211212221222122222222222212222222222222222222222222222222222111111211121121222122212222222222221222222222222222222222222222222222...

result:

ok Correct. (10 test cases)

Test #9:

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

input:

10
100
78 52 95 76 96 49 53 59 77 100 64 11 9 48 15 17 44 46 21 54 39 68 43 4 32 28 73 6 16 62 72 84 65 86 98 75 33 45 25 3 91 82 2 92 63 88 7 50 97 93 14 22 20 42 60 55 80 85 29 34 56 71 83 38 26 47 90 70 51 41 40 31 37 12 35 99 67 94 1 87 57 8 61 19 23 79 36 18 66 74 5 27 81 69 24 58 13 10 89 30
3...

output:

122222222222222222222222221222222222222222222222222222222222222222222222222221122122122122122222222222222222222222222222222222222222222222222222222222222222222222222222222222222111121122122122222222222222222222222222222222222222222222222222222222222222222222222222222222222221111121122122112222222222...

result:

ok Correct. (10 test cases)

Test #10:

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

input:

5
185
176 145 128 100 85 172 45 103 170 18 19 115 65 156 70 136 22 184 69 126 142 25 5 137 55 31 93 163 58 8 13 149 62 114 165 86 54 169 124 140 134 88 160 77 113 68 150 168 56 112 10 185 57 71 74 138 181 59 183 151 174 33 27 61 82 164 6 34 161 84 178 157 48 1 73 119 146 153 78 135 94 47 95 14 90 10...

output:

211211222222222222222222222222222222222222222222222222222222222222222222112222222222222122221122222222212222222222222221222222222222222222212222222222212222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222221112212222222212221112222222221222222222222...

result:

ok Correct. (5 test cases)

Test #11:

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

input:

5
200
168 131 23 136 98 121 183 12 172 57 84 104 115 19 102 122 159 11 36 196 81 92 128 47 109 130 45 195 193 171 62 126 111 154 118 190 59 123 185 91 90 75 71 116 66 177 82 78 38 165 182 163 151 197 129 103 145 176 175 63 147 93 157 191 31 142 76 88 61 55 180 51 117 14 105 80 140 119 173 4 178 127 ...

output:

122222222222221222222212222222222222222222222222222222222222222222222222222222222222212111211222222222222222221222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222211121122212222...

result:

ok Correct. (5 test cases)

Test #12:

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

input:

3
194
162 24 135 168 10 122 13 151 177 189 54 49 57 178 111 171 40 82 78 139 48 59 187 18 66 33 43 38 83 141 117 7 15 137 42 184 23 182 108 179 87 174 134 173 30 149 169 110 31 183 77 94 14 84 150 107 64 103 188 120 140 50 80 156 193 105 170 55 155 157 161 81 95 4 160 26 131 118 63 32 89 36 17 106 3...

output:

212222121222222212222222222222222222222222222222222222221222222222222222222222222222222222222222222222222222222222222222222222222222222222111212212222222222222222222222222222222222222222222222222222222222222222222212222222222222222222222222222222222122222222222222222222222222222222222222222222222222...

result:

ok Correct. (3 test cases)

Test #13:

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

input:

3
300
243 210 61 250 118 147 32 124 158 207 30 180 141 104 107 45 8 238 128 6 215 22 136 100 72 25 209 98 166 240 48 20 290 185 53 11 157 223 55 173 224 35 9 40 78 189 75 116 108 246 203 162 133 298 143 254 106 81 169 279 146 187 96 154 241 83 252 50 13 139 159 276 278 218 54 21 256 145 150 151 120 ...

output:

112222112212222222222221222222222222222222222222222222222222222222222212222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222221222222222222222212222222222222222222222222222222222111122222222222222212222222222222222222222222222112212...

result:

ok Correct. (3 test cases)

Test #14:

score: 0
Accepted
time: 2ms
memory: 4128kb

input:

2
14
4 2 6 13 12 14 10 9 3 1 11 8 5 7
1 12 7 2 5 4 14 13 6 11 3 8 9 10
354
55 14 267 112 280 42 116 251 214 3 289 244 278 208 213 103 1 340 60 348 32 187 223 53 92 311 221 266 227 158 269 261 160 257 234 107 143 225 319 12 177 182 228 268 307 317 75 322 25 109 129 17 285 203 46 188 263 70 125 27 306...

output:

21222122111222222221211122222222121111221122111111111112111111111111211111111111121111111111112111111111111
222222222222222112222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...

result:

ok Correct. (2 test cases)

Test #15:

score: 0
Accepted
time: 6ms
memory: 4524kb

input:

2
500
67 401 380 460 9 93 425 417 491 233 386 355 126 352 114 207 195 317 446 254 98 180 441 259 232 84 500 365 271 62 135 444 315 379 27 63 103 100 482 282 281 457 161 295 234 321 320 47 407 35 424 456 108 111 116 144 427 452 432 480 42 278 139 405 375 13 296 344 228 335 377 305 19 400 495 349 39 4...

output:

222222212222221222222222222222222222222122222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222221222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...

result:

ok Correct. (2 test cases)

Test #16:

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

input:

2
124
116 119 55 10 34 52 91 60 88 82 22 72 89 32 74 54 65 77 24 16 103 56 71 70 99 113 105 31 47 101 63 104 46 85 124 78 53 87 27 26 18 38 19 80 6 67 95 97 44 7 114 121 102 86 118 93 94 41 117 109 106 66 111 123 5 84 69 48 29 61 42 11 59 35 3 37 83 92 8 23 4 28 40 12 45 120 62 112 43 90 58 57 81 51...

output:

121122212121222222222222222221222222222222222222222222222222222221212222222222222222222222222222222221121221122222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222111221121222222222222222222222222222222222212222221222222222221222222222222...

result:

ok Correct. (2 test cases)

Test #17:

score: 0
Accepted
time: 7ms
memory: 4592kb

input:

2
499
198 243 496 23 384 68 174 76 402 432 291 193 482 264 314 477 383 219 270 197 18 438 409 296 49 282 470 46 38 158 406 204 57 415 5 469 247 126 242 295 372 138 239 186 454 310 447 371 398 274 463 355 229 214 40 480 179 177 19 31 297 381 410 339 226 377 145 71 392 32 6 237 348 466 148 481 309 192...

output:

122222122212222222222222222222222212222222222222222222222222222222222222222222222222222212222222222122222222222211212222222222122222222222222221222222222222222222122222222222222222222222222222222222222222222221222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...

result:

ok Correct. (2 test cases)

Test #18:

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

input:

1
389
287 248 46 18 162 190 172 109 183 90 57 353 245 326 378 313 100 24 239 121 219 23 148 64 44 244 74 315 88 175 179 352 169 331 105 125 166 187 39 182 373 231 350 5 171 156 226 135 137 119 206 377 276 117 10 374 357 73 136 356 238 214 50 268 321 235 87 130 153 299 195 177 246 2 360 210 19 228 10...

output:

222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222221122222222222222222222222...

result:

ok Correct. (1 test case)

Test #19:

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

input:

1
1000
312 82 696 525 590 249 495 576 257 385 313 290 53 975 823 599 431 113 166 680 929 691 371 544 934 133 675 175 410 56 364 574 909 383 295 618 908 995 306 771 415 317 474 536 807 878 424 271 794 204 533 552 527 834 294 659 391 442 297 976 367 726 780 775 601 437 121 329 589 178 143 704 119 961 ...

output:

222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...

result:

ok Correct. (1 test case)

Test #20:

score: 0
Accepted
time: 15ms
memory: 5304kb

input:

1
1000
364 329 995 901 904 36 794 429 944 755 248 358 29 87 255 223 239 868 96 74 562 903 376 4 474 206 406 565 156 369 195 602 287 208 215 888 712 412 160 513 844 125 346 784 48 280 145 154 664 851 97 458 276 381 798 374 852 871 662 975 890 124 110 332 389 78 591 365 483 898 646 123 229 737 312 922...

output:

211222222122222222222222222222222222222222222222222212212222222222222222222222222222222222222222222222222222222222222222222122222222222222222222222222222222222222212222222222222222222222222222222222222222122222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...

result:

ok Correct. (1 test case)

Test #21:

score: 0
Accepted
time: 12ms
memory: 6308kb

input:

1
1000
469 637 369 576 724 45 515 610 103 973 309 634 875 667 124 992 601 207 958 261 558 531 305 216 879 974 968 566 243 427 758 749 916 275 349 563 327 131 648 849 65 546 152 902 833 15 320 177 42 226 669 910 418 957 811 657 521 690 987 437 77 656 976 977 718 394 421 824 506 209 134 58 59 630 769 ...

output:

222222222222222222222222222222222222222222222222122222222222212212222222222222122222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222122222222222222222222222...

result:

ok Correct. (1 test case)

Test #22:

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

input:

1
1000
481 866 174 584 599 873 779 718 651 843 662 429 808 139 529 34 367 430 538 108 920 463 423 316 366 527 393 157 52 936 53 611 806 735 120 667 272 246 605 239 273 253 922 640 309 997 477 993 548 643 147 851 687 684 795 765 998 482 934 990 877 729 897 836 150 416 962 854 946 637 661 776 704 526 ...

output:

result:

ok Correct. (1 test case)

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2024-12-03 05:39:34 | 开源项目