QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#667023#7158. Carnival GeneralWarinchai_s#11 22ms17788kbC++141.5kb2024-10-22 20:47:142024-10-22 20:47:22

Judging History

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

  • [2024-10-22 20:47:22]
  • 评测
  • 测评结果:11
  • 用时:22ms
  • 内存:17788kb
  • [2024-10-22 20:47:14]
  • 提交

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: 1ms
memory: 5580kb

input:

2
0

output:

1 0 

result:

ok correct

Test #2:

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

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: 22ms
memory: 17788kb

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: 1ms
memory: 5724kb

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: 1ms
memory: 7888kb

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: 5688kb

input:

2
0

output:

1 0 

result:

ok correct

Test #7:

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

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: 1ms
memory: 5756kb

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: 5732kb

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%