QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#388506#6108. Permutation ArrangementMladenP#WA 0ms3660kbC++141.7kb2024-04-13 16:24:002024-04-13 16:24:00

Judging History

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

  • [2024-04-13 16:24:00]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3660kb
  • [2024-04-13 16:24:00]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define MAXN 200010
#define K 9
#define INF 1000000010
int a[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;
    for (auto x : s) {
        broj.push_back(x);
    }
    for (int i = 1; i <= N; i++) {
        if (a[i] == -1) {
            poz.push_back(i);
        }
    }
    do {
        for (int i = 0; i < K; i++) a[poz[i]] = -1;
        bool uspeo = true;
        for (int i = 0; i < K; i++) {
            int idx = poz[i];
            int num = broj[i];
            if (num == a[idx-1]-1 || num == a[idx-1]+1 || num == a[idx+1]-1 || num == a[idx+1]+1) {
                uspeo = false;
                break;
            }
            a[idx] = num;
        }
        if (!uspeo) continue;
        for (int i = 1; i <= N; i++) {
            cout << a[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: 0
Wrong Answer
time: 0ms
memory: 3660kb

input:

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

output:

3 1 10 2 8 4 6 9 5 8 

result:

wrong answer 10th numbers differ - expected: '7', found: '8'