QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#388442 | #6108. Permutation Arrangement | MladenP# | WA | 0ms | 3628kb | C++14 | 1.9kb | 2024-04-13 15:43:38 | 2024-04-13 15:43:39 |
Judging History
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'