daily pastebin goal
89%
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. OK, I Understand
 
Top