QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#388442#6108. Permutation ArrangementMladenP#WA 0ms3628kbC++141.9kb2024-04-13 15:43:382024-04-13 15:43:39

Judging History

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

  • [2024-04-13 15:43:39]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3628kb
  • [2024-04-13 15:43:38]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define MAXN 200010
#define K 6
#define INF 1000000010
int a[MAXN], b[MAXN];
set<int> s;
int main() {
    int N; cin >> N;
    for (int i = 1; i <= N; i++) {
        s.insert(i);
        cin >> a[i];
    }
    for (int i = 1; i <= N; i++) {
        s.erase(a[i]);
    }
    a[0] = INF;
    a[N+1] = INF;
    for (int i = 1; i <= N && s.size() > K; i++) {
        if (a[i] == -1) {
            int t = -1;
            for (auto x : s) {
                if (x != a[i-1]+1 && x != a[i-1]-1 && x != a[i+1]+1 && x != a[i+1]-1) {
                    t = x;
                    break;
                }
            }
            if (t == -1) {
                cerr << "FUUUUUUUUUUUUUUUUUUUUUCK";
                return 1;
            }
            a[i] = t;
            s.erase(t);
        }
    }
    vector<int> poz, broj, perm;
    for (auto x : s) {
        broj.push_back(x);
        //cerr << "BROJ " << x << endl;
    }
    int idx = 0;
    for (int i = 1; i <= N; i++) {
        if (a[i] == -1) {
            perm.push_back(idx);
            idx++;
            poz.push_back(i);
            //cerr << "POZ " << i << endl;
        }
    }
    do {
        //cerr << "PERM\n";
        for (int i = 1; i <= N; i++) b[i] = a[i];
        bool uspeo = true;
        for (int i = 0; i < K; i++) {
            int idx = poz[i];
            int num = broj[i];
            //cerr << "COMBO " << idx << ' ' << num << endl;
            if (num == b[idx-1]-1 || num == b[idx-1]+1 || num == b[idx+1]-1 || num == b[idx+1]+1) {
                uspeo = false;
                break;
            }
            b[idx] = num;
        }
        if (!uspeo) continue;
        for (int i = 1; i <= N; i++) {
            cout << b[i] << ' ';
        }
        return 0;
    } while (next_permutation(broj.begin(), broj.end()));
    cout << -1;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0ms
memory: 3628kb

input:

2
-1 -1

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3564kb

input:

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

output:

4 1 5 8 6 2 10 7 9 3 

result:

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