QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#666829 | #7158. Carnival General | Khiem# | 29 | 0ms | 4116kb | C++14 | 1.3kb | 2024-10-22 20:07:52 | 2024-10-22 20:07:54 |
Judging History
answer
#include <bits/stdc++.h>
#define z exit(0)
using namespace std;
const int N = 1005;
vector<int> g[N];
int a[N], dp[256][8], V[N];
pair<int,int> up[256][8];
signed main(){
int n; scanf("%d", &n);
for(int i = 1; i<n; ++i){
for(int j = 0; j<i; ++j) scanf("%d", a+j);
int sz = i/2 + (i&1);
for(int j = 0; j<sz; ++j){
int u = i, v = a[j];
g[u].push_back(v); g[v].push_back(u);
}
}
for(int i = 0; i<n; ++i) dp[1<<i][i] = 1;
int lim = 1<<n;
for(int msk = 0; msk<lim; ++msk){
for(int i = 0; i<n; ++i){
if(msk>>i&1){
int pmsk = msk ^ (1<<i);
for(int j: g[i]){
if(pmsk>>j&1 && dp[pmsk][j]){
dp[msk][i] = 1;
up[msk][i] = {pmsk, j};
break;
}
}
}
}
}
int msk = lim-1, j, m = 0;
for(int i = 0; i<n; ++i) if(dp[msk][i]){ j = i; break;}
for(; ; ){
V[m++] = j;
if(__builtin_popcount(msk) == 1) break;
pair<int,int> tmp = up[msk][j];
msk = tmp.first; j = tmp.second;
}
for(int i = m-1; ~i; --i) printf("%d ", V[i]);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 11
Accepted
time: 0ms
memory: 3792kb
input:
2 0
output:
1 0
result:
ok correct
Test #2:
score: 0
Runtime Error
input:
99 0 1 0 2 1 0 3 2 1 0 4 3 2 1 0 5 4 3 2 1 0 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 10 9 8 7 6 5 4 3 2 1 0 11 10 9 8 7 6 5 4 3 2 1 0 12 11 10 9 8 7 6 5 4 3 2 1 0 13 12 11 10 9 8 7 6 5 4 3 2 1 0 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 16 1...
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #6:
score: 23
Accepted
time: 0ms
memory: 3860kb
input:
2 0
output:
1 0
result:
ok correct
Test #7:
score: 0
Runtime Error
input:
99 0 0 1 0 1 2 0 1 2 3 0 1 2 3 4 0 1 2 3 4 5 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 8 9 10 11 12 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 ...
output:
result:
Subtask #3:
score: 29
Accepted
Test #12:
score: 29
Accepted
time: 0ms
memory: 3816kb
input:
2 0
output:
1 0
result:
ok correct
Test #13:
score: 29
Accepted
time: 0ms
memory: 3804kb
input:
8 0 1 0 2 1 0 3 2 1 0 4 3 2 1 0 5 4 3 2 1 0 6 5 4 3 2 1 0
output:
7 6 5 4 3 2 1 0
result:
ok correct
Test #14:
score: 29
Accepted
time: 0ms
memory: 3804kb
input:
8 0 0 1 0 1 2 0 1 2 3 0 1 2 3 4 0 1 2 3 4 5 0 1 2 3 4 5 6
output:
6 2 5 1 4 0 7 3
result:
ok correct
Test #15:
score: 29
Accepted
time: 0ms
memory: 3828kb
input:
8 0 0 1 0 1 2 2 1 0 3 4 3 0 2 1 4 3 0 5 2 1 6 5 2 1 4 0 3
output:
6 7 2 4 5 3 1 0
result:
ok correct
Test #16:
score: 29
Accepted
time: 0ms
memory: 4116kb
input:
8 0 1 0 0 1 2 3 2 1 0 0 1 2 3 4 5 4 3 2 1 0 0 1 2 3 4 5 6
output:
7 3 4 6 5 2 1 0
result:
ok correct
Test #17:
score: 29
Accepted
time: 0ms
memory: 3792kb
input:
3 0 0 1
output:
2 0 1
result:
ok correct
Test #18:
score: 29
Accepted
time: 0ms
memory: 4100kb
input:
5 0 1 0 0 2 1 1 3 2 0
output:
4 3 2 1 0
result:
ok correct
Test #19:
score: 29
Accepted
time: 0ms
memory: 3792kb
input:
6 0 0 1 0 1 2 0 2 1 3 0 2 3 4 1
output:
4 2 5 3 1 0
result:
ok correct
Test #20:
score: 29
Accepted
time: 0ms
memory: 3820kb
input:
7 0 1 0 2 0 1 2 0 1 3 0 1 4 2 3 3 2 4 0 5 1
output:
5 4 6 3 2 1 0
result:
ok correct
Test #21:
score: 29
Accepted
time: 0ms
memory: 3832kb
input:
8 0 1 0 0 1 2 3 2 0 1 3 1 0 4 2 4 2 0 3 5 1 6 4 3 1 5 2 0
output:
5 3 7 6 4 2 1 0
result:
ok correct
Test #22:
score: 29
Accepted
time: 0ms
memory: 3764kb
input:
8 0 0 1 2 1 0 3 0 2 1 4 0 3 1 2 4 0 2 5 3 1 4 5 1 2 0 6 3
output:
7 5 4 6 2 3 1 0
result:
ok correct
Test #23:
score: 29
Accepted
time: 0ms
memory: 4076kb
input:
8 0 0 1 0 1 2 3 2 1 0 4 3 2 1 0 5 4 3 2 1 0 6 5 4 3 2 1 0
output:
7 6 5 2 4 3 1 0
result:
ok correct
Test #24:
score: 29
Accepted
time: 0ms
memory: 3868kb
input:
8 0 1 0 2 1 0 0 1 2 3 0 1 2 3 4 0 1 2 3 4 5 0 1 2 3 4 5 6
output:
6 2 5 1 4 0 7 3
result:
ok correct
Test #25:
score: 29
Accepted
time: 0ms
memory: 3888kb
input:
8 0 1 0 1 0 2 1 3 0 2 1 3 0 2 4 1 3 5 0 2 4 1 3 5 0 2 4 6
output:
2 1 4 3 6 5 7 0
result:
ok correct
Test #26:
score: 29
Accepted
time: 0ms
memory: 4068kb
input:
6 0 1 0 2 1 0 3 2 1 0 4 3 2 1 0
output:
5 4 3 2 1 0
result:
ok correct
Test #27:
score: 29
Accepted
time: 0ms
memory: 3792kb
input:
5 0 0 1 0 1 2 0 1 2 3
output:
4 1 3 0 2
result:
ok correct
Test #28:
score: 29
Accepted
time: 0ms
memory: 3796kb
input:
4 0 1 0 0 2 1
output:
3 2 1 0
result:
ok correct
Subtask #4:
score: 0
Skipped
Dependency #1:
0%