QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#666979#7158. Carnival GeneralWarinchai_s#11 25ms17856kbC++141.5kb2024-10-22 20:37:392024-10-22 20:37:47

Judging History

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

  • [2024-10-22 20:37:47]
  • 评测
  • 测评结果:11
  • 用时:25ms
  • 内存:17856kb
  • [2024-10-22 20:37:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int r[1005][1005];
int no[1005][1005];
vector<int>adj[1005];
vector<int>rv[1005];
int in[1005];
int vis[1005];
int bf[1005];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
int st=0;
int cnt=0;
int n;
void dfs(int u,int p=-1){
    bf[u]=p;
    st=u;
    cnt++;
    int mn=1e4,id=-1;
    for(auto x:adj[u])if(x!=p)if(!vis[x]&&in[x]<mn)mn=in[x],id=x;
    if(id==-1){
        assert(cnt==n);
        return;
    }
    vis[id]=1;
    dfs(id,u);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){
        //cerr<<"i:"<<i<<"\n";
        for(int j=0;j<i;j++){
            cin>>r[i][j];
            if(j>(i/2)){
                no[i][r[i][j]]=1;
                no[r[i][j]][i]=1;
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)continue;
            if(!no[i][j])adj[i].push_back(j),rv[j].push_back(i),in[j]++;
        }
    }
    for(int i=0;i<n;i++){
        pq.push({in[i],i});
    }
    auto [a,b]=pq.top();
    pq.pop();
    vis[b]=1;
    dfs(b);
    int x=0;
    vector<int>v;
    while(st!=-1){
        //cout<<st<<" ";
        v.push_back(st);
        st=bf[st];
    }
    assert(v.size()==n);
    for(int i=1;i<n;i++){
        assert(no[v[i]][v[i-1]]==0);
    }
    map<int,int>mp;
    for(auto x:v){
        assert(mp[x]==0);
        mp[x]++;
    }
    for(auto x:v)cout<<x<<" ";
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 11
Accepted

Test #1:

score: 11
Accepted
time: 0ms
memory: 5636kb

input:

2
0

output:

1 0 

result:

ok correct

Test #2:

score: 11
Accepted
time: 1ms
memory: 6348kb

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:

48 50 49 52 51 47 54 53 46 56 55 58 57 45 60 59 44 62 61 64 63 43 66 65 42 68 67 70 69 41 72 71 40 74 73 76 75 39 78 80 79 82 81 84 83 86 85 88 87 90 89 92 91 94 93 96 95 98 97 77 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 

result:

ok correct

Test #3:

score: 11
Accepted
time: 25ms
memory: 17856kb

input:

1000
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...

output:

500 499 498 502 501 504 503 497 506 505 496 508 507 510 509 495 512 511 494 514 513 516 515 493 518 517 492 520 519 522 521 491 524 523 490 526 525 528 527 489 530 529 488 532 531 534 533 487 536 535 486 538 537 540 539 485 542 541 484 544 543 546 545 483 548 547 482 550 549 552 551 481 554 553 480 ...

result:

ok correct

Test #4:

score: 11
Accepted
time: 0ms
memory: 5748kb

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:

4 3 6 7 5 2 1 0 

result:

ok correct

Test #5:

score: 11
Accepted
time: 0ms
memory: 5716kb

input:

6
0
1 0
2 1 0
3 2 1 0
4 3 2 1 0

output:

2 4 5 3 1 0 

result:

ok correct

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 23
Accepted
time: 1ms
memory: 5856kb

input:

2
0

output:

1 0 

result:

ok correct

Test #7:

score: 0
Wrong Answer
time: 1ms
memory: 6160kb

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:

1 97 0 95 2 93 3 91 4 89 5 87 6 85 7 83 8 81 9 79 10 77 11 75 12 73 13 71 14 69 15 67 16 65 17 63 18 61 19 59 20 57 21 55 22 53 23 51 24 50 25 52 26 54 27 56 28 58 29 60 30 62 31 64 32 66 33 68 34 70 35 72 36 74 37 76 38 78 39 80 40 82 41 84 42 86 43 88 44 90 45 92 46 94 47 96 48 98 49 

result:

wrong answer Enemies 51 and 26 are next to each other

Subtask #3:

score: 0
Wrong Answer

Test #12:

score: 29
Accepted
time: 1ms
memory: 5696kb

input:

2
0

output:

1 0 

result:

ok correct

Test #13:

score: 29
Accepted
time: 0ms
memory: 5964kb

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:

4 3 6 7 5 2 1 0 

result:

ok correct

Test #14:

score: 0
Wrong Answer
time: 1ms
memory: 5720kb

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:

7 1 6 3 0 5 2 4 

result:

wrong answer Enemies 7 and 4 are next to each other

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%