• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Jan 20th, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. //
2. //  최종순위.cpp
3. //  algorithm
4. //
5. //  Created by 김민영 on 2019. 1. 19..
6. //  Copyright © 2019년 김민영. All rights reserved.
7. //
8.
9. #include <stdio.h>
10. #include <string.h>
11. #include<iostream>
12. #include<queue>
13.
14. using namespace std;
15.
16.
17. void solved(){
18.
19.     int t,m;
20.
21.     scanf("%d", &t);
22.
23.     int size = t+1;
24.
25.     int lastYearRankHash[size];
26.     memset(lastYearRankHash, 0, sizeof(lastYearRankHash));
27.
28.     int rankNext[size][size];
29.     int connect[size];
30.     for(int i =0; i<size; i++){
31.         memset(rankNext[i], 0, sizeof(rankNext[i]));
32.     }
33.     memset(connect, 0, sizeof(connect));
34.
35.     //작년 순위
36.     for(int i=1; i<size; i++){
37.         int team;
38.         scanf("%d", &team);
39.         lastYearRankHash[team] = i;
40.
41.         for(int j=1; j<size; j++){
42.             if(lastYearRankHash[j]) continue;
43.             rankNext[team][j] = 1;
44.             connect[j]++;
45.         }
46.     }
47.
48.
49.     scanf("%d", &m);
50.
51.     //변경순위
52.     for(int i =0; i<m; i++){
53.         int team1, team2;
54.         scanf("%d %d", &team1, &team2);
55.         if(!rankNext[team1][team2]){
56.             rankNext[team1][team2] = 1;
57.             connect[team1]--;
58.
59.             rankNext[team2][team1] = 0;
60.             connect[team2]++;
61.         }else{
62.             rankNext[team1][team2] = 0;
63.             connect[team1]++;
64.
65.             rankNext[team2][team1] = 1;
66.             connect[team2]--;
67.         }
68.     }
69.
70.     queue<int> Q;
71.
72.     for(int i =1 ;i<size; i++){
73.         if(connect[i]==0) Q.push(i);
74.     }
75.
76.     int result[t], r = 0;
77.     memset(result, 0, sizeof(result));
78.
79.
80.     while (!Q.empty()) {
81.         if(Q.size()>1){
82.             printf("?\n");
83.             return;
84.         }
85.
86.         int team = Q.front();
87.         Q.pop();
88.
89.         result[r++] = team;
90.
91.         for(int i=1; i<size; i++){
92.             if(!rankNext[team][i]) continue;
93.             rankNext[team][i] = 0;
94.             connect[i]--;
95.             if(!connect[i]) Q.push(i);
96.         }
97.
98.     }
99.
100.     if(r<t){
101.         printf("IMPOSSIBLE\n");
102.         return;
103.     }
104.
105.
106.     for(int i =0 ; i<t; i++){
107.         printf("%d ", result[i]);
108.     }
109.     printf("\n");
110. }
111.
112. int main(){
113.     int testCase;
114.     scanf("%d", &testCase);
115.
116.     for(int i =0; i<testCase; i++){
117.         solved();
118.     }
119.
120. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top