QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#425696#6108. Permutation ArrangementHKOI0#WA 1ms3876kbC++141.8kb2024-05-30 15:53:352024-05-30 15:53:35

Judging History

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

  • [2024-05-30 15:53:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3876kb
  • [2024-05-30 15:53:35]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

bool valid(vector<int>& a, int i, int x){
    int n = a.size();
    if (i > 0 && abs(a[i - 1] - x) == 1) return false;
    if (i < n - 1 && abs(a[i + 1] - x) == 1) return false;
    return true;
}

void solve() {
    int N; cin >> N;
    vector<int> a;
    for (int i = 0; i < N; i++) {
        int v; cin >> v;
        a.push_back(v);
    }
    set<int> rem;
    for (int i = 1; i <= N; i++) {
        rem.insert(i);
    }
    for (int i = 0; i < N; i++) {
        if (a[i] != -1) rem.erase(a[i]);
    }

    int cnt = count(all(a), -1);

    for (int i = 0; i < N && cnt > 7; i++) {
        if (a[i] != -1) continue;
        for (auto x : rem) {
            if (valid(a, i, x)) {
                a[i] = x;
                rem.erase(x);
                break;
            }
            --cnt;
        }
    }

    vector<int> pos, val;

    for (int i = 0; i < N; i++) if (a[i] == -1) pos.push_back(i);
    val = vector<int>(all(rem));

    sort(all(val));

    do {
        for (int i = 0; i < val.size(); i++) {
            a[pos[i]] = val[i];
        }
        bool ok = true;
        for (int i = 0; i < val.size(); i++) {
            ok &= valid(a, pos[i], val[i]);
        }
        if (ok) {
            for (auto x : a) {
                cout << x << ' ';
            }
            cout << endl;
            return;
        }
    } while(next_permutation(all(val)));
    cout << -1 << endl;
}

signed main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

詳細信息

Test #1:

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

input:

10
3 -1 10 -1 8 -1 -1 -1 -1 -1

output:

3 1 10 2 8 4 6 9 5 7 

result:

ok 10 numbers

Test #2:

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

input:

2
-1 -1

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

input:

10
-1 -1 -1 8 -1 2 10 -1 -1 3

output:

1 4 6 8 5 2 10 7 9 3 

result:

ok 10 numbers

Test #4:

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

input:

10
-1 2 -1 6 -1 1 -1 5 -1 3

output:

4 2 8 6 9 1 7 5 10 3 

result:

ok 10 numbers

Test #5:

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

input:

10
-1 3 -1 -1 5 -1 9 -1 -1 -1

output:

1 3 6 2 5 7 9 4 8 10 

result:

ok 10 numbers

Test #6:

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

input:

10
4 -1 8 -1 -1 3 -1 9 -1 6

output:

4 1 8 5 10 3 7 9 2 6 

result:

ok 10 numbers

Test #7:

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

input:

1000
80 360 454 409 303 639 154 486 365 955 -1 -1 625 488 726 -1 94 348 57 -1 287 472 551 981 106 381 199 877 660 736 762 207 -1 59 437 -1 -1 343 593 -1 151 225 -1 -1 430 854 771 378 785 -1 668 617 404 272 -1 871 305 920 507 101 -1 376 123 959 293 327 286 416 77 677 388 336 53 833 932 633 855 744 25...

output:

80 360 454 409 303 639 154 486 365 955 5 21 625 488 726 27 94 348 57 45 287 472 551 981 106 381 199 877 660 736 762 207 55 59 437 64 66 343 593 70 151 225 71 79 430 854 771 378 785 87 668 617 404 272 97 871 305 920 507 101 103 376 123 959 293 327 286 416 77 677 388 336 53 833 932 633 855 744 257 112...

result:

ok 1000 numbers

Test #8:

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

input:

1000
678 -1 739 723 -1 -1 226 881 -1 923 -1 80 568 648 16 480 114 400 -1 527 221 171 931 783 937 959 192 552 363 -1 -1 874 734 940 393 -1 733 915 327 117 -1 190 637 -1 -1 -1 808 300 350 658 720 437 525 -1 -1 876 699 428 493 314 883 139 833 22 252 274 -1 83 -1 376 950 -1 732 476 706 561 837 174 318 7...

output:

678 3 739 723 5 7 226 881 12 923 13 80 568 648 16 480 114 400 19 527 221 171 931 783 937 959 192 552 363 21 23 874 734 940 393 25 733 915 327 117 28 190 637 32 34 36 808 300 350 658 720 437 525 35 48 876 699 428 493 314 883 139 833 22 252 274 51 83 60 376 950 64 732 476 706 561 837 174 318 772 70 74...

result:

ok 1000 numbers

Test #9:

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

input:

1000
-1 585 392 262 972 807 128 -1 558 -1 -1 678 600 472 -1 -1 -1 233 958 -1 -1 651 -1 622 739 -1 151 -1 93 935 -1 55 120 200 755 -1 674 -1 -1 1 -1 -1 -1 -1 -1 446 -1 -1 -1 605 -1 263 -1 43 491 -1 -1 -1 -1 982 -1 388 556 -1 589 -1 -1 448 -1 -1 -1 607 -1 -1 -1 -1 -1 -1 750 40 -1 -1 555 872 -1 -1 -1 5...

output:

2 585 392 262 972 807 128 3 558 6 9 678 600 472 10 12 15 233 958 13 16 651 17 622 739 19 151 20 93 935 21 55 120 200 755 22 674 24 26 1 25 28 30 32 29 446 31 34 37 605 35 263 41 43 491 44 48 50 58 982 49 388 556 51 589 59 62 448 66 71 74 607 75 78 76 79 83 85 750 40 84 88 555 872 89 92 90 535 94 97 ...

result:

ok 1000 numbers

Test #10:

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

input:

1000
202 -1 -1 -1 -1 377 -1 -1 -1 -1 205 -1 -1 -1 470 -1 -1 -1 -1 151 869 678 72 -1 834 -1 -1 37 626 670 -1 902 178 -1 -1 389 500 732 -1 -1 676 109 533 -1 -1 812 731 618 -1 -1 4 108 513 948 312 -1 388 -1 629 -1 190 316 544 237 53 -1 -1 -1 -1 -1 358 226 -1 -1 783 -1 -1 875 634 772 212 56 -1 839 808 2...

output:

202 1 3 5 8 377 6 9 11 14 205 15 20 16 470 21 23 26 22 151 869 678 72 24 834 27 29 37 626 670 28 902 178 31 34 389 500 732 32 36 676 109 533 38 40 812 731 618 39 41 4 108 513 948 312 42 388 43 629 46 190 316 544 237 53 47 52 54 57 55 358 226 58 62 783 63 68 875 634 772 212 56 69 839 808 254 70 73 37...

result:

ok 1000 numbers

Test #11:

score: -100
Wrong Answer
time: 1ms
memory: 3688kb

input:

1000
-1 -1 -1 -1 -1 -1 -1 209 570 -1 552 -1 -1 -1 611 908 536 -1 663 -1 -1 487 -1 -1 -1 -1 -1 -1 365 -1 -1 -1 -1 918 24 -1 -1 -1 973 -1 -1 286 474 -1 585 349 -1 -1 605 735 367 -1 -1 -1 -1 -1 -1 -1 -1 -1 473 -1 489 -1 -1 662 283 -1 -1 -1 -1 -1 -1 -1 -1 -1 260 -1 987 -1 -1 -1 -1 -1 -1 681 -1 -1 -1 -1 ...

output:

-1

result:

wrong answer 1st numbers differ - expected: '1', found: '-1'